#include<bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int INF = 0x3f3f3f3f;
vector< pair<int,int>>G[50005];
set< pair<int,int>>Drum;
int n,m,Dist[50005];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    memset(Dist,INF,sizeof(Dist));
    Dist[1]=0;
    Drum.insert(make_pair(0,1));
    while(!Drum.empty())
    {
        int node=Drum.begin()->second;
        Drum.erase(Drum.begin());
        for(vector<pair<int,int>>::iterator it=G[node].begin();it<G[node].end();++it)
        {
            int cost=it->second;
            int catre=it->first;
            if(Dist[catre]>Dist[node]+cost)
            {
                if(Dist[catre]!=INF)
                {
                    Drum.erase(Drum.find(make_pair(Dist[catre],catre)));
                }
                Dist[catre]=Dist[node]+cost;
                Drum.insert(make_pair(Dist[catre],catre));
            }
        }
    }
    for(int i=2;i<=n;++i)
        if(Dist[i]==INF)
        g<<0<<' ';
    else
        g<<Dist[i]<<' ';

}