#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <utility>

using namespace std;

ifstream fin ("djikstra.in");
ofstream fout ("djikstra.out");

#define MAXN 50050
#define INFTY 9999999

vector < pair <int,int> > edge[MAXN];
set < pair <int, int> > solution;
int N, M, Gdistance[MAXN];

void Djikstra(int node)
{
    for (int i = 0; i < node; ++i)
		Gdistance[i] = INFTY;
    for (int i = node+1; i <= N; ++i)
		Gdistance[i] = INFTY;

    solution.insert(make_pair(node, 0));

    while (!solution.empty())
    {
    	pair <int, int> top = *solution.begin();
    	node = top.first;
    	int cost = top.second;
    	solution.erase(top);
    	for (int i = 0; i < edge[node].size(); ++i)
			if (Gdistance[edge[node][i].first] > cost + edge[node][i].second)
			{
				Gdistance[edge[node][i].first] = cost + edge[node][i].second;
				solution.insert(make_pair(edge[node][i].first,
											Gdistance[edge[node][i].first]));
			}
    }


}

int main()
{
    fin >>N >>M;
    for (int i = 1; i <= M; ++i)
	{
		int x, y, c;
		fin >>x >>y >>c;
        edge[x].push_back(make_pair(y,c));
	}
	Djikstra(1);
	for (int i = 1; i <= N; ++i)
		fout << (Gdistance[i] != INFTY) ? (Gdistance[i]) : 0;
    return 0;
}