#include<fstream>
#include<vector>
#define inf 2000000000
using namespace std;
vector <pair <int, int> > L[50003];
int t, n, m2, i, x, y, z, D[50003], h[50003], p[50003], dh, nrm, m[50003], k, vecin, cost, s, p1, aux;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int main(){
    in>>n>>m2;
    for(i=1; i<=m2; i++){
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
    }
    for(i=2; i<=n; i++)
        D[i]=inf;
    h[1]=1;
    p[1]=1;
    dh=1;
    while(1){
        if(dh==0)
            break;


        m[h[1]]=1;
        k=h[1];
        //nrm++;

        // scot varful din heap

        h[1] = h[dh];
        dh--;

        p1=1;
        s=2;
        while(s<=dh){
            if(s+1<=dh && D[h[s]]>D[h[s+1]])
                s++;
            if(D[h[p1]]>D[h[s]]){
                aux=h[p1];
                h[p1]=h[s];
                h[s]=aux;
                p[h[p1]]=p1;
                p[h[s]]=s;
            } else
                break;

            p1=s;
            s*=2;
        }
        p[k] = -1;

        for (i=0;i<L[k].size();i++) {
            vecin = L[k][i].first;
            cost = L[k][i].second;

            if (D[vecin] > D[k] + cost) {
                D[vecin] = D[k] + cost;
                if (p[vecin] >= 1 && p[vecin] <= dh) {
                    t = p[vecin];
                } else {
                    dh++;
                    h[dh] = vecin;
                    p[ vecin ] = dh;
                    t = dh;
                }

                if (dh!=1 && D[ h[t/2] ] > D[ h[t] ]) {
                    // urc
                    s = t;
                    p1 = t/2;
                    while(p1>0){
                        if (D[ h[p1] ] > D[ h[s] ]){
                            aux=h[p1];
                            h[p1]=h[s];
                            h[s]=aux;
                            p[h[p1]]=p1;
                            p[h[s]]=s;
                        }
                        s=p1;
                        p1/=2;
                    }
                } else {
                    // cobor
                    p1 = t;
                    s = 2*t;
                    while(s<=dh){
                        if(s+1<=dh && D[h[s]]>D[h[s+1]])
                            s++;
                        if (D[ h[p1] ] > D[ h[s] ]){
                            aux=h[p1];
                            h[p1]=h[s];
                            h[s]=aux;
                            p[h[p1]]=p1;
                            p[h[s]]=s;
                        }
                        p1=s;
                        s*=2;
                    }
                }
            }
        }
    }
    for(i=2; i<=n; i++)
        out<<D[i]<<" ";
return 0;
}