#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <ctype.h>
using namespace std;
ofstream cout("dijkstra.out");
class InParser {

private:

	FILE* fin;

	char* buff;

	int sp;



	char read_ch() {

		++sp;

		if (sp == 4096) {

			sp = 0;

			fread(buff, 1, 4096, fin);

		}

		return buff[sp];

	}



public:

	InParser(const char* nume) {

		fin = fopen(nume, "r");

		buff = new char[4096]();

		sp = 4095;

	}



	InParser& operator >> (int& n) {

		char c;

		while (!isdigit(c = read_ch()) && c != '-');

		int sgn = 1;

		if (c == '-') {

			n = 0;

			sgn = -1;

		}
		else {

			n = c - '0';

		}

		while (isdigit(c = read_ch())) {

			n = 10 * n + c - '0';

		}

		n *= sgn;

		return *this;

	}



	InParser& operator >> (long long& n) {

		char c;

		n = 0;

		while (!isdigit(c = read_ch()) && c != '-');

		long long sgn = 1;

		if (c == '-') {

			n = 0;

			sgn = -1;

		}
		else {

			n = c - '0';

		}

		while (isdigit(c = read_ch())) {

			n = 10 * n + c - '0';

		}

		n *= sgn;

		return *this;

	}

};
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

bool spfa(int s, vector<int>& d) {
	int n = adj.size();
	d.assign(n, INF);
	vector<int> cnt(n, 0);
	vector<bool> inqueue(n, false);
	queue<int> q;

	d[s] = 0;
	q.push(s);
	inqueue[s] = true;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		inqueue[v] = false;

		for (auto edge : adj[v]) {
			int to = edge.first;
			int len = edge.second;

			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				if (!inqueue[to]) {
					q.push(to);
					inqueue[to] = true;
					cnt[to]++;
					if (cnt[to] > n)
						return false;
				}
			}
		}
	}
	return true;
}
int n, m, x, y, z;
int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
	InParser cin("dijkstra.in");
    cin >> n >> m;
    adj.resize(n);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        x--; y--;
        adj[x].push_back({ y,z });
    }
	vector<int> ans;
	spfa(0, ans);
    for (int i = 1; i < ans.size(); i++)
    {
        if (ans[i] != INF)
            cout << ans[i];
        else cout << '0';
        cout << ' ';
    }
    return 0;
}