#include <bits/stdc++.h>
#define vecin vec.first
#define distanta vec.second

using namespace std;
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");
const int N = 50010;
const int oo=1000000010;
vector<pair<int,int>> v[N];
int n,m,x,y,c,d[N];
priority_queue<pair<int,int> > q;
bitset<N> viz;
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(int i=2; i<=n; i++)
        d[i]=oo;
    q.push(make_pair(0,1));
    while(q.size())
    {
        tie(c,x)=q.top();
        q.pop();
        if(viz[x])
            continue;
        viz[x]=1;
        d[x]=-c;
        for(auto vec:v[x])
            if(!viz[vecin])
                if(d[x]+distanta<d[vecin])
                {
                    d[vecin]=d[x]+distanta;
                    q.push(make_pair(-d[vecin],vecin));
                }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==oo)
            d[i]=0;
        g<<d[i]<<' ';
    }
    return 0;
}