#include <bits/stdc++.h>
#define ff first
#define ss second
#define inf 1000000001
#define NMAX 50001
#define MMAX 250001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int, int> > v[NMAX];
priority_queue< pair< int, int > >coada;
int check[NMAX];
int n,m;
int d[NMAX];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for(int i=2;i<=n;++i)d[i]=inf;
    coada.push({0,1});
    while(!coada.empty())
    {
        int t;
        t=coada.top().ss;
        check[t]=0;
        coada.pop();
        for(auto x: v[t])
        {
            if(d[x.ff]>d[t]+x.ss)
            {
                d[x.ff]=d[t]+x.ss;
                if(!check[x.ff])coada.push({-d[x.ff],x.ff}),check[x.ff]=1;
            }
        }
    }
    for(int i=2;i<=n;++i,fout<<" ")if(d[i]==inf)fout<<0;else fout<<d[i];
    return 0;
}