#include <bits/stdc++.h>
#define PII pair <int, int>
#define INF INT_MAX / 2

using namespace std;

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

int n, m, d[50005];
vector <PII> edges[50005];
priority_queue <PII, vector <PII>, greater <PII>> pq;

void dijkstra(int nod){
    for(int i = 1; i <= n; i++)
        d[i] = INF;
    d[nod] = 0;
    pq.push({0, nod});
    while(!pq.empty()){
        nod = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(cost != d[nod])
            continue;
        for(auto k : edges[nod])
            if(d[k.first] > cost + k.second){
                d[k.first] = cost + k.second;
                pq.push({d[k.first], k.first});
            }
    }

}
int main()
{

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