#include <cstdio>
#include <cstdlib>
#include <vector>
#define DIM 50001 
#define INF 1<<29 
using namespace std ;
 
struct nod
{
    int cap,dist;
};
nod arbint[3*DIM],x,infinit,temp;
vector <nod> v[DIM];
int n,m;
int drum[DIM];
int p,u;
int viz[DIM];
 
 
nod minim (nod x, nod y)
{
    if ( x.dist<y.dist) return x;
        else return y;
}
void actualizare ( int nod_nou , int st , int dr , int a , nod b )
{
    if (st==dr)
        arbint[nod_nou]=b;
        else
        {
            int pivot=(st+dr )/2;
            if (a<=pivot) actualizare (2*nod_nou,st,pivot,a,b) ;
                else actualizare(2*nod_nou+1 ,pivot+1,dr,a,b) ;
            arbint[nod_nou]=minim(arbint[2*nod_nou],arbint[2*nod_nou+1]);
        }
}
 
void dijkstra ( int nod )
{
    if (viz[nod]==0) return;
    viz[nod]=0;
 
    actualizare(1,1,n,nod,infinit);
 
 
    for (int i=0;i<v[nod].size();++i)
    {
        int nod_nou=v[nod][i].cap ;
        int muchie=v[nod][ i ].dist ;
        int antdist=drum[nod_nou];
 
        if (antdist>drum[nod]+muchie)
            {
                drum[nod_nou]=drum[nod]+muchie;
                temp.cap = nod_nou ;
                temp.dist = drum[nod_nou];
                actualizare (1,1,n,nod_nou,temp) ;
            }
 
    }
 
   // nod=arbint[1].cap ;
    dijkstra(nod);
 
}
void setinf_arbint (int nod,int st,int dr)
{
    if (st==dr)
        arbint[nod]=infinit;
        else
            {
                int pivot=(st+dr)/2 ;
                setinf_arbint(2*nod,st,pivot);
                setinf_arbint(2*nod+1,pivot+1,dr);
                arbint[nod]=minim(arbint[2*nod],arbint[2*nod+1]);
            }
}
void setdist ()
{
    viz[1]=1;
    drum[1]=0;
 
    for (int i=2;i<=n;++i)
    {
        viz[i]=1;
        drum[i]=infinit.dist ;
    }
}

void print()
{

for ( int i=2;i<=n;i++)
        if (drum[i]!=infinit.dist) printf("%d ",drum[i]);
            else printf ("0 ");
}
 
int main ()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf ("%d %d",&n,&m) ;
    for (int i=1;i<=m;++i)
    {
        int a ;
        nod temp ;
        scanf("%d %d %d",&a,&temp.cap,&temp.dist);
        v[a].push_back(temp);
    }
 
    infinit.dist=INF;
    infinit.cap=0;
    setdist();
    setinf_arbint(1,1,n) ;
    arbint[1].cap=1;
    //arbint[1].dist=infinit.dist;
    dijkstra ( 1 ) ;
	
	print();
     
 
  
 
}