//cu heap=uri
#include<fstream>
#include<vector>
#define infin 250000002

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

int v[50002];
struct muchie
{
    int inf;
    int cost;
};
     
vector <muchie> lv[50002];
int pret[50002],aux, n, mm, poz[50002],heap[50002],ordin[50002],k=0,j=0;

void add(int cost,int nod)
{   
    poz[nod]=++j;
    ordin[j]=nod;
    heap[j]=cost;
    int j2;
    j2=j;
    while(j>1&&heap[j/2]>heap[j])
        {
            int aux;
            aux=heap[j/2];
            heap[j/2]=heap[j];
            heap[j]=aux;
            poz[ordin[j/2]]=j;
            poz[ordin[j]]=j/2;
            aux=ordin[j/2];
            ordin[j/2]=ordin[j];
            ordin[j]=aux;
            j=j/2;
        }
    j=j2;
}
void update(int x,int cost)
{
    int j2;
    j2=poz[x];
    heap[j2]=cost;
    while(j2>1&&heap[j2/2]>heap[j2])
        {
            int aux;
            aux=heap[j2/2];
            heap[j2/2]=heap[j2];
            heap[j2]=aux;
            poz[ordin[j2/2]]=j2;
            poz[ordin[j2]]=j2/2;
            aux=ordin[j2/2];
            ordin[j2/2]=ordin[j2];
            ordin[j2]=aux;
            j2=j2/2;
        }
}
 
void remove(int x)
{ 
    int u,p,aux;
    u=poz[x];
    heap[u]=heap[j];
    heap[j]=0;
    ordin[u]=ordin[j];
    poz[ordin[j]]=u;
    j--;
    while(heap[2*u]&&(heap[2*u]<heap[u]||(heap[2*u+1]&&heap[2*u+1]<heap[u])))
	{
		if(heap[2*u+1]&&heap[2*u+1]<heap[2*u])
			p=2*u+1;
		else 
			p=2*u;
		aux=heap[p];
		heap[p]=heap[u];
		heap[u]=aux;
		poz[ordin[p]]=u;
		poz[ordin[u]]=p;
		aux=ordin[p];
		ordin[p]=ordin[u];
		ordin[u]=aux;
		u=p;
	}
}
 
 
int main()
{
    int i;
     
    f>>n>>mm;
	
    for(i=1;i<=mm;i++)
    {   
        int x;
        muchie y;
        f>>x>>y.inf>>y.cost;
        lv[x].push_back(y);
    }
	
    add(0,1);
	
    pret[1]=0;
    for(i=2;i<=n;i++)
	{
		add(infin,i);
		pret[i]=infin;
	}
     
    int j, n1;
	
    n1=n;
    while(n1)
    {
		int cine,cat;
		cine=ordin[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;
				update(lv[cine][i].inf,pret[lv[cine][i].inf]);
			}
		}
		remove(cine);
		n1--;
	}
	
	for(i=2;i<=n;i++)
	{
		if(pret[i]!=infin)
			g<<pret[i]<<" ";
		else
			g<<"0 ";
	}
	
    return 0;
}