#include <bits/stdc++.h>
#define vec it.first
#define cst it.second
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int N = 50010;
const int oo = 1000000010;
bitset<N> used;
vector< pair< int, int > > v[N];
int n,m,x,y,i,c,d[N];
bool crit(int i,int j){return d[i]>d[j];}
class comp
{
    public : bool operator()(int i,int j){return d[i]<=d[j];}
};
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    fill(d+2,d+n+1,oo);
    priority_queue< int, vector<int>, comp > q;
    q.push(1);
    while(q.size())
    {
        x=q.top();q.pop();
        if(used[x])
            continue;
        used[x]=1;
        for(auto it:v[x])
        if(d[vec]>d[x]+it.second)
        {
            d[vec]=d[x]+it.second;
            q.push(it.first);
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==oo)d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}