#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define inf 1e9
using namespace std;
FILE *fin, *fout;
vector <pair <int,int> >g[50009];
priority_queue <pair <int,int> >v;
int ap[50009], d[50009];
void disj (int a) {
    ap[a]=1;
    d[a]=0;
    v.push(make_pair(0, a));
    while (!v.empty()) {
        a=v.top().second;
        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[next]>d[a]+cost) {
                d[next]=d[a]+cost;
                if (ap[next]==0) {
                    v.push(make_pair(-d[next], next));
                    ap[next]=1;
                }
            }
        }
        ap[a]=0;
    }
}
int main()
{
    int n, i, m, 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]=inf;
    }
    disj(1);
    for (i=2;i<=n;i++) {
        if (d[i]==inf) {
            fprintf(fout, "0 ");
        }
        else
        fprintf(fout, "%d " ,d[i]);
    }
    cout << "Hello world!" << endl;
    return 0;
}