#include<iostream>
#include<fstream> 
#define MARE 100000000
 using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
 
int a[1501][1501],s[1501],d[1501],i,m,n,l,c;
 
void dijkstra (int linie) {
    int min, dmin, jmin, j;
 
    for (i = 1; i <= n; i++)
        d[i] = a[linie][i];     
    s[linie] = 1; 
    d[linie] = 0;   
    for (i = 2; i <= n; i++) {
        min = MARE;
        for (j = 1; j <= n; j++) 
            if (!s[j])           
                if (min > d[j]) {    
                    min = d[j];        
                    jmin = j;          
                }
        s[jmin] = 1; 
        for (j = 1; j <= n; j++)     
            if (!s[j]) {             
                dmin = d[jmin]+a[jmin][j]; 
                if (d[j] > dmin)          
                    d[j] = dmin;             
            }
    }
}
 
int main () {
    f >> n >> m;
    for (l = 1; l <= n; l++)
        for (c = 1; c <= n; c++)
            a[l][c] = MARE;
    for (i = 1; i <= m; i++) {
        f >> l >> c;
		f >> a[l][c];
    }
    dijkstra(1);
    for (i = 2; i <= n; i++) {
      if (d[i] == MARE)
      g << "0 ";
    else
      g << d[i] << ' ';
    }
}