#include<bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int>> G[50005];
set<pair<int,int>> h;
int inf=1000000000,d[50005],x,y,c,n,m,i,crt,cost,nod;

int main()
{
	fin>>n>>m;
	for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
	memset(d,inf,sizeof d);
	d[1]=0;
		h.insert(make_pair(0,1));
		while(!h.empty())
		{
			crt=h.begin()->second;
			h.erase(h.begin());
			for(i=0;i<G[crt].size();i++)
			{
				nod=G[crt][i].first;
				cost=G[crt][i].second;
				if(d[crt]+cost<d[nod])
				{
					if(d[nod]!=inf) h.erase(h.find(make_pair(d[nod],nod)));
					d[nod]=d[crt]+cost;
					h.insert(make_pair(d[nod],nod));
				}
			}
		}
	
	  for (i=2; i<=n; i++)
    {
        if (d[i]==inf) d[i]=0;
       fout<<d[i];
    }
	return 0;
}