#include <fstream>
#include <queue>
#include <climits>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX = 50005;
int e[NMAX][NMAX], dist[NMAX];
int n, m;
void dijkstra(){
    queue<pair<int, int>> Q;
    dist[1] = 0;
    Q.push({1, 0});

    while(!Q.empty()){
        int nod = Q.front().first, d = Q.front().second;
        Q.pop();

        if(dist[nod] < d)
            continue;

        for(int i=1; i<=n; i++)
            if(e[nod][i] != -1){
                dist[i] = min(dist[i], dist[nod] + e[nod][i]);
                Q.push({i, dist[nod] + e[nod][i]});
            }
    }
}
int main(){
    in>>n>>m;
    for(int i=1; i<=n; i++)
        dist[i] = INT_MAX;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            e[i][j] = -1;

    for(int i=1; i<=m; i++){
        int a, b;
        in>>a>>b;
        in>>e[a][b];
    }

    dijkstra();
    for(int i=2; i<=n; i++)
        out<<(dist[i] != INT_MAX ? dist[i] : 0)<<" ";
    return 0;
}