#include<fstream>
#include<vector>
#define infin 250000003

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int v[50002];

struct muchie
{
    int inf;
    int cost;
};
     
vector <muchie> lv[500002];

int pret[50002], arb[132000], n, mm;
 
void actualizare(int nod,int st,int dr,int x,int cost)
{
	if( st == dr )
		arb[nod]=cost;
   else
   {
		int m;
		m=(st+dr)/2;
		if(x<=m)
			actualizare(2*nod,st,m,x,cost);
        else 
		    actualizare(2*nod+1,m+1,dr,x,cost);
     
		if(arb[2*nod]<arb[2*nod+1])
			arb[nod]=arb[2*nod];
        else
			arb[nod]=arb[2*nod+1];
   }
}
     
void construire(int nod,int st, int dr)
{
	if(st==dr)
	{
		if(st==1)
			arb[nod]=0;
		else 
			arb[nod]=infin;
		pret[st]=infin;
	}
    else
	{
        int m;
        m=(st+dr)/2;
        construire(nod*2,st,m);
        construire(nod*2+1,m+1,dr);
    
		if(arb[2*nod]<arb[2*nod+1])
			arb[nod]=arb[2*nod];
         else 
			arb[nod]=arb[2*nod+1];
        }
}

int minim(int nod, int st,int dr)
{
	if(st==dr)
		return st;
	else
    { 
		int m;
		m=(st+dr)/2;
		if(arb[2*nod]<arb[2*nod+1])
			return minim(2*nod,st,m);
		else 
			return minim(2*nod+1,m+1,dr);
	}
}
 
int main()
{
    int i;
     
    f>>n;
    f>>mm;
    for(i=1;i<=mm;i++)
    {   
        int x;
        muchie y;
        f>>x>>y.inf>>y.cost;
        lv[x].push_back(y);
         
    }
     
    int j;
     
    construire(1,1,n);
    
	while(arb[1]!=infin)
    {
		int cine, cat;
		cine=minim(1,1,n);
		pret[cine]=arb[1];
		v[cine]=1;
		cat=lv[cine].size();
		for(i=0;i<cat;i++)
		{
			if( !v[lv[cine][i].inf] && pret[cine]+lv[cine][i].cost < pret[lv[cine][i].inf] )
			{
				pret[lv[cine][i].inf]=pret[cine]+lv[cine][i].cost;
				actualizare(1,1,n,lv[cine][i].inf,pret[lv[cine][i].inf]);
			}
		}
		actualizare(1,1,n,cine,infin);
	}
      
	for(i=2;i<=n;i++)
		if(pret[i]!=infin)
			g<<pret[i]<<" ";
		else g<<"0 ";
		
    return 0;
}