#include <bits/stdc++.h>
#define INF 99999
#define MAX 51000
//here we go again

using namespace std;

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

vector < pair <int, int> > G[MAX];;

int n, m;
int dijkstra[MAX];

void go(){
    priority_queue < pair < int, int > , vector < pair < int, int > >, greater < pair < int, int > > > pchiu;
    pchiu.push({0,1});
    while(!pchiu.empty()){
        int nod = pchiu.top().second;
        int valuare = pchiu.top().first;
        pchiu.pop();

        if (dijkstra[nod] != valuare) continue;
        for (int i = 0; i < G[nod].size(); i++){
            if (valuare + G[nod][i].second < dijkstra[G[nod][i].first]){
                dijkstra[G[nod][i].first] = valuare + G[nod][i].second;
                pchiu.push({dijkstra[G[nod][i].first], G[nod][i].first});
            }
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i =  1; i <= m; i++){
        int x, y, d;
        f >> x >> y >> d;
        G[x].push_back({y, d});
    }
    for (int i = 2; i <= n; i++){
        dijkstra[i] = INF;
    }
    go();
    for (int i = 2; i <= n; i++){
        if (dijkstra[i] == INF){
            g << "0 ";
        } else {
            g << dijkstra[i] << ' ';
        }
    }
    return 0;
}