#include <iostream>
#include <vector>
#include <list>

#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;
typedef pair<int,int> pereche;
typedef list<pereche> lista;

lista G[NMAX];
int M,N;

class cHeap
{
	
private:
	vector<int> heap,pozitie,distanta;
	int iHeap;
	
public:
	
	cHeap(void)
	{
		heap=vector<int>(NMAX);
		pozitie=vector<int>(NMAX,-1);
		distanta=vector<int>(NMAX,DMAX);
		iHeap=0;
	}
	
	void Up(int fiu)
	{
		for(int tata=fiu>>1;fiu&&distanta[heap[fiu]]<distanta[heap[tata]];fiu>>=1,tata=fiu>>1)
		{
			swap(pozitie[heap[fiu]],pozitie[heap[tata]]);
			swap(heap[fiu],heap[tata]);
		}
	}
	
	void Down(int fiu)
	{
		int st,dr,_min;
		for(;;)
		{
			st=fiu<<1;
			dr=st+1;
			_min=st;
			
			if(st>=iHeap)
				return;
			else if(dr<iHeap&&distanta[heap[st]]>distanta[heap[dr]])
				_min=dr;
			
			if(distanta[heap[fiu]]>distanta[heap[_min]])
			{
				swap(pozitie[heap[fiu]],pozitie[heap[_min]]);
				swap(heap[fiu],heap[_min]);
			}
			else
				return;
		}
	}
	
	void Push(int fiu,int dist)
	{
		distanta[fiu]=dist;
		heap[iHeap]=fiu;
		pozitie[fiu]=iHeap++;
		Up(iHeap-1);
	}
	
	int Pop()
	{
		int fiu=heap[0];
		heap[0]=heap[--iHeap];
		Down(0);
		pozitie[fiu]=-1;
		return fiu;
	}
	
	int& operator[](int fiu)
	{
		return distanta[fiu];
	}
	
	bool HasElements()
	{
		return iHeap>0;
	}
	
	void Insert(int fiu,int dist)
	{
		if(pozitie[fiu]==-1)
			Push(fiu,dist);
		else
			distanta[fiu]=dist,
			Up(pozitie[fiu]);
	}	
}dijkstra;

void citire(),rezolvare(),afisare();

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	citire();
	rezolvare();
	afisare();
	
	return 0;
}

void afisare()
{
	for(int i=2;i<=N;i++)
	{
		if(dijkstra[i]!=DMAX)
			cout<<nounitbuf<<dijkstra[i]<<" ";
		else
			cout<<"0 ";
	}
}

void rezolvare()
{
	dijkstra.Push(1,0);
	while(dijkstra.HasElements())
	{
		int fiu=dijkstra.Pop();
		for(lista::iterator it=G[fiu].begin();it!=G[fiu].end();it++)
			if(dijkstra[(*it).first]>dijkstra[fiu]+(*it).second)
				dijkstra.Insert((*it).first,dijkstra[fiu]+(*it).second);
	}
}

void citire()
{
	int s,d,c;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)
	{
		scanf("%d %d %d",&s,&d,&c);
		G[s].push_back(pereche(d,c));
	}
}