#include <bits/stdc++.h>

using namespace std;
typedef pair <int,int> pii;
priority_queue <pii> pq;
vector <pii> muchii[50001];
int n,m;
int dist[50001];
void Dijkstra(){
    int i;
    for(i = 2;i <= n;i++){
        dist[i] = 2e9;
    }
    dist[1] = 0;
    pq.push({0,1});
    while(!pq.empty()){
        int nod = pq.top().second;
        int distanta = pq.top().first;
        pq.pop();
        for(auto x : muchii[nod]){
            if(distanta + x.second < dist[x.first]){
                dist[x.first]  = distanta + x.second;
                pq.push({dist[x.first],x.first});
            }
        }
    }
}
int main()
{

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int i;
    cin >> n >> m;
    for(i = 1;i <= m;i++){
        int x,y,z;
        cin >> x >> y >> z;
        muchii[x].push_back({y,z});
    }
    Dijkstra();
    for(i = 2;i <= n;i++){
        cout << dist[i] << " ";
    }
    return 0;
}