#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define inf 1<<24
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    int n, m;
    f>>n>>m;
    vector <vector <pair <int, int> > > v(n+1);
    vector < int > d(n+1,inf);
    set < pair < int ,int > > S;
    d[1]=0;
    for (int i=1;i<=m;i++){
        int x,y,cost;
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    S.insert(make_pair(0,1));
    while (!S.empty()){
        int em=(*S.begin()).second;
        for (auto j:v[em]){
            if (d[em]+j.second<d[j.first]){
                S.erase(make_pair(d[j.first],j.first));
                d[j.first]=d[em]+j.second;
                S.insert(make_pair(d[j.first],j.first));
            }
        }
        S.erase(S.begin());
    }
    for (int i=2;i<=n;i++)
        if (d[i]==inf)  g<<"0"<<' ';
        else    g<<d[i]<<' ';

    return 0;
}