#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 50001;
const int M = 250001;
const int INF = 1e9;

int vf[M], urm[M], cost[M], lst[N], d[N], nr, n;
bool visited[N];

priority_queue <pair<int, int> > h;

void adauga(int x, int y, int c){
    vf[++nr] = y;
    cost[nr] = c;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dijkstra(int x0){
    for(int i=1; i<=n; i++)
        d[i] = INF;
    d[x0] = 0;
    h.push(make_pair(0,x0));
    while(!h.empty()){
        if(visited[h.top().second] == true){
            h.pop();
            continue;
        }
        int node = h.top().second;
        visited[node] = true;
        h.pop();
        for(int p=lst[node]; p!=0; p=urm[p]){
            int next = vf[p];
            int c = cost[p];
            if(d[node] + c < d[next]){
                d[next] = d[node] + c;
                h.push(make_pair(-d[next], next));
            }
        }
    }
}

int main()
{
    FILE *fin, *fout;
    int m,i,x,y,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",&x,&y,&c);
        adauga(x,y,c);
    }
    dijkstra(1);
    for(i=2; i<=n; i++)
        if(d[i] == INF)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}