using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define oo 0x3f3f3f3f
#define T ((i)/2)
#define L ((i)*2)
#define R ((L)+1)
#define pb push_back
#define nmax 50005
ofstream fout("dijkstra.out");
struct leg{
int n,c;};
vector<leg> G[nmax];

int N,M,nh;
int H[nmax],poz[nmax],d[nmax];

void init()
{
    int i;
    for(i=1;i<=N;i++)
    {

      H[i]=i;
      d[i]=oo;
      poz[i]=i;
    }
    d[1]=0;



}

inline void upheap(int i)
{
    if(i<=1) return;
    if(d[H[T]]>d[H[i]]) swap(H[T],H[i]), swap(poz[H[T]],poz[H[i]]), upheap(T);

}

inline void downheap(int i)
{
    int m=i;

    if(L<=nh)
        if(d[H[L]]<d[H[m]]) m=L;
    if(R<=nh)
        if(d[H[R]]<d[H[m]]) m=R;

    if(m!=i)  swap(H[m],H[i]), swap(poz[H[m]],poz[H[i]]), downheap(m);

}

void dijkstra()
{vector<leg>::iterator it;
int u,i;
     while(nh>=0)
    {
         u=H[1];
         swap(H[1],H[nh]);
         swap(poz[H[1]],poz[H[nh]]);
         nh--;

         downheap(1);
         for(it=G[u].begin();it!=G[u].end();it++)
         {
             if(d[it->n]>d[u]+it->c)
             {
                 d[it->n]=d[u]+it->c;
                 upheap(poz[it->n]);
             }
         }


    }
    for(i=2;i<=N;i++)
     if(d[i]==oo)
      fout<<0<<" ";
      else
      fout<<d[i]<<" ";
}

void cit()
{    int i,x,y,c;
    ifstream fin("dijkstra.in");

    fin>>N>>M;
    nh=N;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        G[x].pb((leg){y,c});


    }
    fin.close();

}


int main()
{


    cit();
    init();
    dijkstra();
    return 0;
}