#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
FILE *fin, *fout;
char ap[50003];
int d[50003], n, m;
struct da {
    bool operator () (int x, int y) {
        return d[x]>d[y];
    }
};
vector <pair <int,int> >g[50003];
priority_queue < int, vector <int>, da > v;
void dijkstra(int a) {
    ap[a]=1;
    d[a]=0;
    v.push(a);
    while(!v.empty()) {
        //fprintf(fout, "%d " ,a);
        a=v.top();
        ap[a]=1;
        v.pop();
        for (int i=0;i<g[a].size();i++) {
            int next=g[a][i].first;
            int cost=g[a][i].second;
            if (d[a]+cost<d[next]) {
                d[next]=d[a]+cost;
                if (ap[next]==0) {
                    v.push(next);
                    ap[next]=1;
                }
            }
        }
    }
}
int main()
{
    int i, a, b, c;
    fin=fopen("dijkstra.in" ,"r");
    fout=fopen("dijkstra.out" ,"w");
    fscanf(fin, "%d%d" ,&n ,&m);
    for (i=0;i<m;i++) {
        fscanf(fin, "%d%d%d" ,&a ,&b ,&c);
        g[a].push_back(make_pair(b,c));
    }
    for (i=1;i<=n;i++) {
        d[i]=1000000009;
    }
    dijkstra(1);
    /*for (i=1;i<=n;i++) {
        for (int l=0;l<g[i].size();l++) {
            fprintf(fout, "%d " ,g[i][l].first);
        }
        fprintf(fout, "\n");
    }*/
    for (i=2;i<=n;i++) {
        if (d[i]==1000000009) {
        fprintf(fout, "0 ");
        }
        else {
        fprintf(fout, "%d " ,d[i]);
        }
    }
    cout << "Hello world!" << endl;
    return 0;
}