#include<fstream>
#include<vector>
using namespace std;
int n,m,vf=1;
const int INF=1<<30;
int sol[50010],heap[50010],unde[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)
{while(i>1&&cmp(heap[father(i)],heap[i]))
	{swap(heap[i],heap[father(i)]);
	swap(unde[heap[i]],unde[heap[father(i)]]);
	i=father(i);
	}
}
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]);
		swap(unde[heap[son]],unde[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]=INF,i++);
heap[1]=1;unde[1]=1;
while(vf>0)
	{nod=heap[1];
	heap[1]=heap[vf--];
	unde[heap[1]]=1;
	down(1);
	for(j=0;j<vecin[nod].size();j++)
		{vec=vecin[nod][j];
		 if(sol[vec]==INF)
		     heap[++vf]=vec,unde[vec]=vf,sol[vec]=sol[nod]+cost[nod][j],up(vf);
		 else if(sol[vec]>sol[nod]+cost[nod][j])
				{sol[vec]=sol[nod]+cost[nod][j];
				up(unde[vec]);
				}
		}
	}
}
int main()
{
citire();
dijkstra();
ofstream out("dijkstra.out");
for(int i=2;i<=n;i++)
	{if(sol[i]==INF)
		sol[i]=0;
	out<<sol[i]<<" ";
	}
out<<'\n';
out.close();
return 0;
}