#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;

	}

};
struct Edge {
    int to, w;
};

vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p,int n) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                }
                else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}
int n, m, x, y, z;
int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(0);
	InParser cin("file.in");
    cin >> n >> m;
    adj.resize(n+1);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        x--; y--;
        adj[x].push_back({ y,z });
    }
    vector<int> ans, p;
    shortest_paths(0, ans, p, n);
    for (int i = 1; i < ans.size(); i++)
    {
        if (ans[i] != INF)
            cout << ans[i];
        else cout << '0';
        cout << ' ';
    }
    return 0;
}