#include <bits/stdc++.h>
#define Dim 50004
#define oo 1<<30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N,M,D[Dim],x,y,c;
bool  viz[Dim];
vector < pair < int,int > > Vf[Dim];

struct comp
{
    bool operator()(int X,int Y)
    {
        return D[X]>=D[Y];
    }
};

priority_queue < int, vector < int > , comp > C;

void Citire()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
       f>>x>>y>>c;
       Vf[x].push_back(make_pair(y,c));
    }
    for(int i=1;i<=N;i++) D[i]=oo;
}

void Dijkstra()
{
   C.push(1);
   D[1]=0;
   viz[1]=1;
   while(!C.empty())
   {
       int nod_curent=C.top();
       C.pop();
       viz[nod_curent]=1;
       for(unsigned int i=0;i<Vf[nod_curent].size();i++)
       if(D[Vf[nod_curent][i].first]>D[nod_curent]+Vf[nod_curent][i].second)
       {
           D[Vf[nod_curent][i].first]=D[nod_curent]+Vf[nod_curent][i].second;
           if(viz[Vf[nod_curent][i].first]==0)
           {
             C.push(D[Vf[nod_curent][i].first]);
             viz[Vf[nod_curent][i].first]=1;
           }
       }
   }
}

int main()
{
    Citire();
    Dijkstra();
    for(int i=2;i<=N;i++)
    if(D[i]!=oo) g<<D[i]<<" ";
    else  g<<0;
    return 0;
}