#include <fstream>
#include <vector>
#define father(nod) (nod/2)
#define left_son(nod) (nod*2)
#define right_son(nod) (nod*2+1)
#define NMAX 50010
#define MMAX 250002
#define MAX 1<<29
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m;
int heap[2*NMAX],viz[NMAX];
vector < pair<int, int> > list[MMAX];
int drum[MMAX];
vector < pair<int, int> >::iterator it;

void swap(int H[],int a,int b)
{int aux;
aux=H[a];
H[a]=H[b];
H[b]=aux;
}

void sift(int H[],int N,int K)
{
int son;
do
  {
  son=0;

  if (left_son(K) <= N)
     {
     son=left_son(K);
     if (( right_son(K)<=N ) && (drum[H[right_son(K)]] < drum[H[left_son(K)]]))
      son=right_son(K);
     }

  if (drum[H[son]]>=drum[H[K]]) son=0;

  if (son)
     {
     swap(H,son,K);
     K=son;
     }
  } while (son);
}

void percolate(int H[],int N,int K)
{
while ( ( drum[H[K]]<drum[H[father(K)]] ) && (father(K)>=1) )
 {swap(H,K,father(K));
 K=father(K);
 }

}



void del(int H[],int &N,int K)
{

H[K]=H[N];N--;
if ( (K>1) && (drum[H[K]]>drum[H[father(K)]]) )
     percolate(H,N,K);
else
     sift(H,N,K);
}

void add(int H[],int &N,int val)
{
N++;
H[N]=val;
percolate(H,N,N);


}
int main()
{
    int i,a,b,init,c,dh=0;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        list[a].push_back(make_pair(b,c));
    }
    for (i=2;i<=n;i++)
        drum[i]=MAX;

    add(heap,dh,1);

    while (dh)
        {
        init=heap[1];
        del(heap,dh,1);
            for(it=list[init].begin();it!=list[init].end();it++)
                if (drum[(*it).first]>drum[init]+(*it).second)
                    {
                        drum[(*it).first]=drum[init]+(*it).second;
                        add(heap,dh,(*it).first);
                    }

        }
    for (i=2;i<=n;i++)
        if (drum[i]!=MAX) g<<drum[i]<<" ";
            else g<<"0 ";

return 0;
}