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