#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];
priority_queue< pair< int, int > > q;
int n,m,x,y,i,c,d[N];
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);
    q.push(make_pair(0,1));
    while(q.size())
    {
        tie(c,x)=q.top();q.pop();
        c=-c;
        if(used[x])
            continue;
        used[x]=1;
        for(auto it:v[x])
        if(d[vec]>c+cst)
        {
            d[vec]=c+cst;
            q.push(make_pair(-d[vec],vec));
        }

    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==oo)d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}