#include <iostream>
#include <fstream>
#define INF 0x3f3f3f3f
#define maxn 50005


using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, edge[maxn/10][maxn/10];
int dist[maxn];
bool sptSet[maxn];

int minDistance(){

    int minim = INF, min_index;

    for(int i = 1; i <= n; ++i){

        if(!sptSet[i] && dist[i] <= minim){
            minim = dist[i];
            min_index = i;
        }
    }

    return min_index;

}

void dijkstra(int src){

    for(int i = 1; i <= n; ++i){
        dist[i] = INF;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for(int i = 1; i <= n; ++i){

        int u = minDistance();

        sptSet[u] = true;

        for(int j = 1; j <= n; ++j){

            if(!sptSet[j] && dist[u] + edge[u][j] < dist[j]){
                dist[j] = dist[u] + edge[u][j];
            }
        }
    }

}

int main(){

    f >> n >> m;

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            edge[i][j] = INF;
        }
    }

    for(int i = 1; i <= m; ++i){

        int x, y, d;
        f >> x >> y >> d;
        edge[x][y] = d;
    }

    dijkstra(1);

    for(int i = 2; i <= n; ++i) g << dist[i] << ' ';

}