#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

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

typedef pair<int, int> pi;

int n, m;
vector<int> dist;
vector<int> visited;
vector<vector<pi>> edges;

class Comparator
{
public:
    bool operator () (const pi& a, const pi& b) const
    {
        return a.second < b.second;
    }
};

void Dijkstra(int nod)
{
    priority_queue<pi, vector<pi>, Comparator> q;
    q.push({nod, 0});
    dist[nod] = 0;

    while (!q.empty())
    {
        pi p = q.top(); q.pop();

        if (visited[p.first])
            continue;

        visited[p.first] = true;

        for (vector<pi>::iterator it = edges[p.first].begin(); it != edges[p.first].end(); ++it)
        {

            int node = it->first;
            int cost = it->second;
            if (dist[node] > dist[p.first] + cost)
            {
                dist[node] = dist[p.first] + cost;
                q.push({node, dist[node]});
            }
        }
    }
}

int main()
{
    fin >> n >> m;

    dist.resize(n + 1, INF);
    visited.resize(n + 1, false);
    edges.resize(m + 1, vector<pi>());

    for (int i = 1, x, y, c; i <= m; ++i)
    {
        fin >> x >> y >> c;
        edges[x].push_back({y, c});
    }

    Dijkstra(1);

    for (int i = 2; i <= n; ++i)
        if (dist[i] == INF)
            fout << 0 << " ";
        else
            fout << dist[i] << " ";

    return 0;
}