using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
ofstream fout("dijkstra.out");
#define pb push_back
struct nod{
	int lg,c;
};
#define nmax 50005
#define mmax 250005
#define oo 0x3f3f3f3f
#define L ((i)*2)
#define T ((i)/2)
#define R ((i)*2+1)
vector<nod> G[nmax];
int N,M;
int nh;
int H[nmax],poz[nmax],d[nmax];
void upheap(int i)
{
  if(i<=1) return;
  if(d[H[i]]<d[H[T]])
  {swap(H[i],H[T]);
  swap(poz[H[i]],poz[H[T]]);
  upheap(T);
  }  
}

void downheap(int i)
{
	int m=i;
	
	if(L<=nh) 
	{
		if(d[H[L]]<d[H[i]])
		{
			m=L;
	    }
	}
    if(R<=nh)
	{
		if(d[H[R]]<d[H[i]])
		{
			m=R;
		}
	}		
	
	if(i!=m) swap(H[i],H[m]), swap(poz[H[i]],poz[H[m]]), downheap(m);
		
}
void solve()
{   int u,i;
	vector<nod>::iterator it;
	for(i=1;i<=N;i++)
	{
		d[i]=oo;
		poz[i]=i;
		H[i]=i;
	}
	d[1]=0;
	nh=N;
	while(nh)
	{
		u=H[1];
		swap(H[1],H[nh]);
		swap(poz[H[1]],poz[H[nh]]);
		nh--;
		downheap(poz[H[1]]);/////<==========
	    for(it=G[u].begin();it<G[u].end();it++)
		{
			if(d[it->lg]>d[u]+it->c)
			{
				d[it->lg]=d[u]+it->c;
				upheap(poz[it->lg]);
			}
		}
	}
	for(i=2;i<=N;i++)
		  fout<<d[i]<<" ";
	fout<<"\n";
}

void cit()
{int x,y,c,i;
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	for(i=1;i<=M;i++)
	{
		fin>>x>>y>>c;
		G[x].pb((nod){y,c});
	}
	fin.close();
	
}

int main()
{
	cit();
	solve();
	fout.close();
	
	return 0;
}