#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,c;
vector< pair<int,int> >a[250250];
int rez[60000];
set< pair<int,int> > s;
int main(){
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> x >> y >> c;
        a[x].push_back(make_pair(y,c));
    }
    c = 1<<30;
    for (int i = 0; i <= n; i++) rez[i] = c;
    rez[1] = 0;
    s.insert(make_pair(0,1));
    while(!s.empty()){  
        set< pair<int,int> >::iterator it1 = s.begin();
        int f = it1->second;
        s.erase(s.begin());
        for (vector< pair<int,int> >::iterator it = a[f].begin(); it != a[f].end(); it++)   {   
            if (rez[f] + it->second < rez[it->first])  {
                if (rez[it->first]!= c)
                    s.erase(s.find(make_pair(rez[it->first],it->first)));
                rez[it->first] = rez[f] + it->second;
                s.insert(make_pair(rez[it->first], it->first));
            }
        }
    }
    for (int i = 2; i <= n; i++) cout << (rez[i] == 1 <<30 ? 0:rez[i]) << " ";
}