#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];
    bool visited[n+1];
    for(int i = 1;i<=n;i++){
        d[i] = INF;
        d[i] = a[src][i];
        visited[i] = false;
    }
    d[src] = 0;
    int mn = INF;
    int v;
    for(int i = 1;i<=n;i++){
        mn = INF;
        for(int j = 1;j<=n;j++){
            if(!visited[j] && d[j] < mn){
                mn = d[j];
                v = j;
            }
        }
        visited[v] = true;
        for(int k = 1;k<=n;k++){
            if(!visited[k]){
                if(d[k] > a[v][k] + d[v]){
                    d[k] = a[v][k] + d[v];
                }
            }
        }
    }
    for(int i = 2; i<=n;i++){
        if(d[i] == INF){
            of << 0 << " ";
        } else
        of << d[i] << " ";
    }
    f.close();
    of.close();
}