#include<fstream>
#include<vector>
using namespace std;
int n,m,vf=1;
bool v[50010],ind[50010];
int sol[50010],heap[50010];
vector <unsigned short> cost[50010],vecin[50010];
inline int left(int i) {return 2*i;}
inline int right(int i) {return 2*i+1;}
inline int father(int i) {return i/2;}
inline int cmp(int a,int b) {return sol[a]>sol[b];}
inline void swap(int &a,int &b) {int aux;aux=a;a=b;b=aux;}
void up(int i)
{int k=heap[i];
while(i>1&&cmp(heap[father(i)],heap[i]))
	{heap[i]=heap[father(i)];
	i=father(i);
	}
heap[i]=k;
}
void down(int i)
{int son;
do 	{son=0;
	if(left(i)<=vf)
		son=left(i);
	if(right(i)<=vf&&cmp(heap[left(i)],heap[right(i)]))
		son=right(i);
	if(cmp(heap[son],heap[i]))
		son=0;
	if(son)
		{swap(heap[son],heap[i]);
		i=son;
		}
	} while(son) ; 
}
void citire()
{int i,y,x,c;
ifstream in("dijkstra.in");
in>>n>>m;
for(i=0;i<m;i++)
	{in>>x>>y>>c;
	vecin[x].push_back(y);
	cost[x].push_back(c);
	}
in.close();
}
void dijkstra()
{int i,nod=1,vec;
unsigned int j;
for(i=2;i<=n;sol[i]=51123456,i++);
heap[1]=1;
for(i=1;i<=n;i++)
	{nod=heap[1];
	v[nod]=1;
	heap[1]=heap[vf--];
	//down(1);
	make_heap(heap+1,heap+vf);
	for(j=0;j<vecin[nod].size();j++)
		{vec=vecin[nod][j];
		if(!v[vec])
			{if(ind[vec]==0)
				heap[++vf]=vec,ind[vec]=1;
			if(sol[vec]>sol[nod]+cost[nod][j])
				{sol[vec]=sol[nod]+cost[nod][j];
				}
			//up(vf);
			make_heap(heap+1,heap+vf);
			}
		}
	}
}
int main()
{
citire();
dijkstra();
ofstream out("dijkstra.out");
for(int i=2;i<=n;i++)
	{if(sol[i]==51123456)
		sol[i]=0;
	out<<sol[i]<<" ";
	}
out<<'\n';
out.close();
return 0;
}