#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
 
const int N_MAX = 50000 + 5;
const int inf = 0x3f3f3f3f;
vector<pair<int,int> > vec[N_MAX];
priority_queue<pii, vector<pii>, greater<pii> > pq;
int cst[N_MAX];
 
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
 
int n, m;
 
void dijkstra(int start){
    memset(cst, inf, sizeof(cst));
    cst[start] = 0;
    pq.push({0, start});
 
    while(!pq.empty()){
        int cost = pq.top().first;
        int nod = pq.top().second;
        pq.pop();
 
        for(auto v : vec[nod]){
            if(cst[v.first] > cst[nod] + v.second){
                cst[v.first] = cst[nod] + v.second;
                pq.push({cst[v.first], v.first});
            }
        }
    }
}
 
int main()
{
 
    fin >> n >> m;
 
    while(m--){
        int a, b, c;
        fin >> a >> b >> c;
        vec[a].push_back({b,c});
    }
 
    dijkstra(1);
 
    for(int i = 2; i<=n; ++i)
        if(cst[i] < inf)
            fout << cst[i] << " ";
        else
            fout << "0 ";
    return 0;
}