#include <bits/stdc++.h>
#define MAX 50001
using namespace std;

FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");

struct graf{
    int nod,unde,cost;
    graf *next;
};

graf *dest[MAX];
int val[MAX];

int main()
{
    int nr,m,i,j;
    fscanf(in, "%d %d", &nr, &m);

    for(i = 0; i!= m;i++){
        graf *n = new graf;
        fscanf(in, "%d %d %d", &n->nod, &n->unde, &n->cost);
        n->next=dest[n->unde];
        dest[n->nod]= n;
    }

    for(i = 1; i!=nr; i++){
        val[i]=INT_MAX;
    }
    int pmn = 0;
    int q[MAX];
    for(i = 0; i!=nr; i++){
        int mn = INT_MAX;
        for(j = 0; j!=nr; j++)
            if(val[j]< mn && !q[j]){
                mn=val[j];
                pmn = j;
            }
        q[pmn] = 1;

        graf  *nx = dest[pmn];
        while(nx){
            if(val[nx->unde] > val[pmn]+nx->cost)
                val[nx->unde] = val[pmn]+nx->cost;
            nx = nx->next;
        }
    }

    for (i = 1; i != nr; i++ )
        fprintf(out, "%d ", val[i] == INT_MAX ? 0 : val[i]);
    fprintf(out, "\n");


    return 0;
}