Problem: You are given a weighted undirected connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Let's define the weight of the path consisting of k edges with indices e_1, e_2, ..., e_k as ∑_{i=1}^{k}{w_{e_i}} - max_{i=1}^{k}{w_{e_i}} + min_{i=1}^{k}{w_{e_i}}, where w_i — weight of the i-th edge in the graph.

Your task is to find the minimum weight of the path from the 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices and the number of edges in the graph.

Following m lines contains three integers v_i, u_i, w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^9; v_i ≠ u_i) — endpoints of the i-th edge and its weight respectively.

Output

Print n-1 integers — the minimum weight of the path from 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Examples

Input


5 4
5 3 4
2 1 1
3 2 2
2 4 2


Output


1 2 2 4 


Input


6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4


Output


2 1 4 3 1 


Input


7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4


Output


3 4 2 7 7 3 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INFi = 1e9+67;
const ll INFll = 1e18;

using NumberType = double;

namespace {
    struct None {
        friend bool operator<(const None& lhs, const None& rhs) {
            return false;
        }
    };

    struct Edge {
        int to;
    };

    struct WEdge {
        int to;
        ll w;
    };

#define ParEdgeType typename conditional<is_same<EIdType,None>::value, EType, pair<EIdType, EType>>::type
    template<typename EIdType, typename EType>
    struct PFInfo {
        int par = -1;
        ll dist = INFll;
        ParEdgeType parEdge;

        friend bool operator<(const PFInfo& a, const PFInfo& b) {
            return a.dist<b.dist;
        }

        bool isPath() {
            return dist!=INFll;
        }
    };

#define FOR_GRAPH(ReturnType) template<typename EIdType_=EIdType> \
        typename enable_if<is_same<EIdType_, None>::value, ReturnType>::type
#define FOR_BOR(ReturnType) template<typename EIdType_=EIdType> \
        typename enable_if<!is_same<EIdType_, None>::value, ReturnType>::type

    template<typename VType_, typename EType_, typename VIdType=None, typename EIdType=None>
    struct Graph {
        using VType = VType_;
        using EType = EType_;
        vector<VType> v;
        typename conditional<is_same<EIdType, None>::value, vector<vector<EType>>, vector<map<EIdType, EType>>>::type g;
        vector<PFInfo<EIdType, EType>> pf;

        Graph(int n): v(n), g(n), pf(n) {};
        Graph(): Graph(0) {};

        FOR_GRAPH(void) addOEdge(int u, int v, const EType& newE) {g[u].push_back(newE); g[u].back().to = v;}
        FOR_BOR(void) addOEdge(int u, int v, const EType& newE) {assert(false);}
        FOR_GRAPH(void) addEdge(int u, int v, const EType& newE) {addOEdge(u,v, newE);addOEdge(v,u, newE);}
        FOR_BOR(void) addEdge(int u, int v, const EType& newE) {assert(false);}

        FOR_BOR(void) addOEdge(int u, int v, const EIdType& newEId, const EType& newE) {assert(g[u].count(newEId)==0); g[u][newEId] = newE; g[u][newEId].to = v;}
        FOR_GRAPH(void) addOEdge(int u, int v, const EIdType& newEId, const EType& newE) {assert(false);}

        //to update edge after insertion
        FOR_GRAPH(int) addOEdge(int u, int v) {g[u].emplace_back(); g[u].back().to = v; return ((int) g[u].size())-1;};
        FOR_BOR(int) addOEdge(int u, int v) {assert(false);};

        FOR_BOR(int) goTo(int from, const EIdType& eId, const EType& newE) {
            if (!g[from].count(eId)) {
                int to = g.addV();
                addOEdge(from, to, eId, newE);
            }
            return g[from][eId].to;
        }
        FOR_GRAPH(int) goTo(int from, const EIdType& eId, const EType& newE) {assert(false);}

        int addV() {
            int id = v.size();
            v.emplace_back();
            g.emplace_back();
            pf.emplace_back();
            return id;
        }

        map<VIdType, int> ids; //or unordered_map if better
        vector<VIdType> idsBack;

        //if too slow, use external vertex id generator, but don't forget to allocate graph of required size
        int asV(const VIdType& id) {
            if (!ids.count(id)) {
                ids[id] = addV();
                idsBack.push_back(id);
            }
            return ids[id];
        }
        const VIdType& asLabel(int id) {
            return idsBack[id];
        }

        void printAdj() const {
            for (int i=0;i<g.size();i++) {
                cout << i+1 << ": ";
                for (auto& it: g[i]) {
                    cout << it.to+1 << " ";
                }
                cout << "\n";
            }
            cout << endl;
        }
    };
//contains common algorithm to restore path

    template<typename EIdType, typename EType>
    struct Path {
        vector<int> verts;
        vector<ParEdgeType> edges;
    };

    template<typename EIdType, typename EType>
    Path<EIdType, EType> restorePath(const vector<PFInfo<EIdType, EType>>& pfInfo, int to) {
        vector<int> verts;
        vector<ParEdgeType> edges;
        while (true) {
            verts.push_back(to);
            if (pfInfo[to].par == -1) { //Not found
                return {};
            }
            if (pfInfo[to].par == -2) {
                reverse(verts.begin(), verts.end());
                reverse(edges.begin(), edges.end());
                return {verts, edges};
            }
            edges.push_back(pfInfo[to].parEdge);
            to = pfInfo[to].par;
        }
    }
}

namespace std {
    template<typename a, typename b>
    struct hash<std::pair<a, b> > {
    public:
        hash() {}
        size_t operator()(const std::pair<a, b> &p) const {
            return hash<a>()(p.first) + hash<b>()(p.second)*998242353;
        }
    };
};

ll mod = 1e9+7;
//ll mod = 998244353;

using ld = double;

double eps = 1e-9;

const int maxn = 1e6+5;
//const int maxn2 = maxn*maxn;

//double dp[10][maxn][maxn*maxn];

template<typename G>
vector<ll> myDijkstra(G& g, int start) {
    set<pair<ll,int>> s;

    vector<ll> dists(4*g.v.size(), INFll);

    dists[start] = 0;

    s.insert({0,start});

    while (!s.empty()) {
        auto p = *s.begin();
        int v = p.second;

        int hasMin = (v >> 1) & 1;
        int hasMax = v & 1;
        int vert = v >> 2;

        s.erase(p);

        //add edges if need
        for (auto& it: g.g[vert]) {
            int to = it.to;
            ll w = it.w;
            if (dists[v] + w < dists[4*to+hasMin*2+hasMax]) {
                s.erase({dists[4 * to + hasMin * 2 + hasMax], 4 * to + hasMin * 2 + hasMax});
                dists[4 * to + hasMin * 2 + hasMax] = min(dists[4 * to + hasMin * 2 + hasMax], dists[v] + w);
                s.insert({dists[4 * to + hasMin * 2 + hasMax], 4 * to + hasMin * 2 + hasMax});
            }
            if (!hasMin && !hasMax) {
                if (dists[v] + w<dists[4*to+3]) {
                    s.erase({dists[4 * to + 3], 4 * to + 3});
                    dists[4 * to + 3] = min(dists[4 * to + 3], dists[v] + w);
                    s.insert({dists[4 * to + 3], 4 * to + 3});
                }
            }
            if (!hasMin) {
                if (dists[v] + 2*w<dists[4*to+2+hasMax]) {
                    s.erase({dists[4 * to + 2 + hasMax], 4 * to + 2 + hasMax});
                    dists[4 * to + 2 + hasMax] = min(dists[4 * to + 2 + hasMax], dists[v] + 2 * w);
                    s.insert({dists[4 * to + 2 + hasMax], 4 * to + 2 + hasMax});
                }
            }
            if (!hasMax) {
                if (dists[v] <dists[4*to+hasMin*2+1]) {
                    s.erase({dists[4 * to + hasMin * 2 + 1], 4 * to + hasMin * 2 + 1});
                    dists[4 * to + hasMin * 2 + 1] = min(dists[4 * to + hasMin * 2 + 1], dists[v]);
                    s.insert({dists[4 * to + hasMin * 2 + 1], 4 * to + hasMin * 2 + 1});
                }
            }
        }
    }
    return dists;
}

void solve() {
    int n,m;
    cin >> n >> m;
    Graph<None, WEdge> g(n);
    for (int i=0;i<m;i++) {
        int u,v;
        ll w;
        cin >> u >> v >> w;
        u--; v--;
        g.addEdge(u,v, {-1, w});
    }
    auto kekw = myDijkstra(g, 0);
    assert(kekw.size() == 4*n);
    for (int i=1;i<n;i++) {
        cout << kekw[i*4+3] << " ";
    }
}

int main() {
//        freopen("input.txt","w",stdout);
//        int n = 100'000;
//        for (int i=0;i<n;i++) {
//            cout << 1 << " ";
//        }
//        cout << "\n";
//        for (int i=1;i<n;i++) {
//            cout << 1 << " " << i+1 << "\n";
//        }
//        for (int i=0;i<n;i++) {
//            cout << 200'000 << " ";
//        }
    //    cout << 10 << " " << 0 << "\n";
    //    int starsLeft = 5;
    //    for (int i=0;i<10;i++) {
    //        for (int j=0;j<10;j++) {
    //            int kekw = rand() % 20;
    //            if (kekw==1 && starsLeft) {
    //                cout << "*";
    //                starsLeft--;
    //            } else {
    //                cout << ((char) ('0' + (rand() % 10)));
    //            }
    //        }
    //        cout << "\n";
    //    }
//        return 0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     //freopen("input.txt","r",stdin);
    //freopen("output.bin","w",stdout);
    //freopen("/tmp/output.txt","w",stdout);

    cout << setprecision(15) << fixed;
//    int t;
//    cin >> t;
//    for (int i=0;i<t;i++)
        //    ll start = clock();
        //    while (1)
        solve();
    //    double time = (clock() - start) * 1.0 / CLOCKS_PER_SEC;
    //    cout<< time << "s.";
    return 0;
}