#include <bits/stdc++.h>

using namespace std;

int n, m, d[50005];
vector< pair<int, int> > v[50005];
set< pair<int, int> > s;

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    while(m--){
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for (int i = 1; i <= n; ++i)
        d[i] = 2000000000;
    s.insert({0, 1});
    while(!s.empty()){
        int k = s.begin()->second;
        int c = s.begin()->first;
        s.erase(s.begin());
        for (vector< pair<int, int> >::iterator it = v[k].begin(); it != v[k].end(); ++it)
            if(c+it->second < d[it->first]){
                if(s.find({d[it->first], it->first}) != s.end())
                    s.erase(s.find({d[it->first], it->first}));
                d[it->first] = c + it->second;
                s.insert({c+it->second, it->first});
            }
    }
    for (int i = 2; i <= n; ++i)
        fout << (d[i] == 2000000000 ? 0 : d[i]) << " ";
    return 0;
}