#include <fstream>
#include <queue>
#include <vector>

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

const int INF = 0x3f3f3f3f, MAXN = 5005;

int vertexCount, arcCount;

int dist[MAXN], viz[MAXN];
struct comparator {
	bool operator()(int a, int b) {
		return dist[a] > dist[b];
	}
};
priority_queue <int, vector<int>, comparator> heap;

struct arc {
	int link, cost;
};
vector<arc> graph[MAXN];

void input() {
	fin >> vertexCount >> arcCount;
	int from, to, cost;
	for (int i = 1; i <= arcCount; i++)
	{
		fin >> from >> to >> cost;
		graph[from].push_back({ to,cost });
	}
}

void dijkstra(int node) {
	for (arc ARC : graph[node]) {
		if (dist[ARC.link] > ARC.cost + dist[node]) {
			dist[ARC.link] = ARC.cost + dist[node];
			heap.push(ARC.link);
		}
	}
}

void output()
{
	for (int i = 2; i <= vertexCount; i++)
	{
		if (dist[i] == INF)
			dist[i] = 0;
		fout << dist[i];
	}
}

int main() {
	input();
	memset(dist, INF, sizeof(dist));
	dist[1] = 0;
	heap.push(1);
	while (!heap.empty()) {
		dijkstra(heap.top());
		heap.pop();
	}
	output();

	return 0;
}