#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define VM 50005
#define MV (1 << 30)
#define pb push_back
#define mp make_pair
 
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
vector<pii> v[VM];
int n, m, c[VM];
 
priority_queue<pii, vector<pii>, greater<pii> > Heap;
 
int main()
{
    fin>>n>>m;
    for(int i = 1 ; i <= n ; ++i)
        c[i] = MV;
    for(int x, y, cost, i = 0 ; i < m ; ++i){
        fin>>x>>y>>cost;
        v[x].pb(mp(y,cost));
    }
    Heap.push(mp(0,1)); 
    c[1] = 0;
    while(Heap.size()){
        int cost = Heap.top().x;
        int top = Heap.top().y;
        Heap.pop();
        if(cost > c[top])
            continue;
        for(int i = 0 ; i < v[top].size() ; ++i){
            if(c[v[top][i].x] > cost + v[top][i].y){
                c[v[top][i].x] = cost + v[top][i].y;
                Heap.push(mp(cost + v[top][i].y , v[top][i].x));
            }
        }
    }
    for(int i = 2 ; i <= n ; ++i)
        if(c[i] == MV)
            fout<<"0 ";
        else
            fout<<c[i]<<' ';
    return 0;
}