#include<cstdio>
#include<vector>
#include<queue>
#define N 50001
#define M 250001
#define OO 1<<30
using namespace std;
vector <int> a[N],cost[M];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;
int d[N],pred[N],n,m;
bool s[N];
void extinde (int, int);
void citire ()
{
	int x,y,c;
	scanf ("%d%d",&n,&m);
	for (int i=1 ; i<=m ; ++i)
	{
		scanf ("%d%d%d",&x,&y,&c);
		a[x].push_back(y);
		cost[x].push_back(c);
	}
}
void dijkstra (int x)
{
	int i,c;
	for (i=1; i<=n ; ++i)
	{
		d[i]=OO;
	}
	d[x]=0;
	h.push(make_pair(0,x));
	while (!h.empty())
	{
		x=h.top().second;
		c=h.top().first;
		h.pop();
		if (s[x])
			continue;
		s[x]=true;
		extinde (x,c);
	}
}
void extinde (int x, int c)
{
	int y,c1;
	size_t g=a[x].size();
	for (size_t i=0 ; i<g ; ++i)
	{
		y=a[x][i];
		c1=cost[x][i];
		if (c+c1<d[y])
		{
			d[y]=c+c1;
		}
		h.push(make_pair(d[y],y));
		pred[y]=x;
	}
}
void afisare (int x)
{
	int y;
	if (x==0)
	{
		return;
	}
	y=pred[x];
	afisare (y);
	printf ("%d",x);
}
int main () 
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	citire ();
	dijkstra (1);
	for (int i=2 ; i<=n ; ++i)
		printf ("%d",d[i]);
	printf ("\n");
	return 0;
}