#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
fstream f("dijkstra.in", ios::in), g("dijkstra.out", ios::out);
#define INF 0x3f3f3f
typedef pair<int, int> ii;
int n, m;
vector<ii> adj[100001];
int d[100001];
void dijkstra(int x)
{
    priority_queue<ii, vector<ii>, greater<ii> > q;
    q.push(make_pair(0, x));
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    d[x] = 0;
    while (!q.empty())
    {
        int cost = q.top().first, node = q.top().second;
        q.pop();
        if (cost > d[node])
            continue;
        for (auto &cur : adj[node])
        {
            if (d[cur.first] > cost + cur.second)
            {
                d[cur.first] = cost + cur.second;
                q.push(make_pair(d[cur.first], cur.first));
            }
        }
    }
}
signed main()
{
    f >> n >> m;
    int x, y, cost;
    while (m--)
    {
        f >> x >> y >> cost;
        adj[x].push_back(make_pair(y, cost));
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++)
        if (d[i] == INF)
            g << -1 << ' ';
        else
            g << d[i] << ' ';
}