#include <iostream>
#include <fstream>

using namespace std;

const int INF = 1000000;

int main(){
    ifstream f("dijkstra.in");
    ofstream of("dijkstra.out");
    int n,m;
    f >> n >> m;
    int a[n+1][n+1];
    int src = 1;
    int x,y,c;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            a[i][j] = INF;
        }
    }
    for(int i = 1;i<=m;i++){
        f >> x >> y >> c;
        a[x][y] = c;
    }
    int d[n+1];
    for(int i = 1;i<=n;i++){
        d[i] = INF;
        d[i] = a[src][i];
    }
    d[src] = 0;
    int mn = INF;
    for(int i = 1;i<=n;i++){
        for(int k = 1;k<=n;k++){
            if(d[i] > a[k][i] + d[k]){
                d[i] = a[k][i] + d[k];
            }
        }
    }
    for(int i = 2; i<=n;i++){
        of << d[i] << " ";
    }
    f.close();
    of.close();
}