#include <fstream>
#include <queue>
#include <vector>
#include <list>
#include <limits>

using namespace std;

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int n, m;
    in >> n >> m;

    vector<list<pair<int, int> > > adj(n+1);

    int x, y, c;
    for (int i = 0; i < m; ++i) {
        in >> x >> y >> c;

        adj[x].push_back(make_pair(y, c));
    }

    priority_queue<pair<int, int> > pq;
    constexpr int INF = numeric_limits<int>::max();
    vector<int> dist(n+1, INF);
    vector<bool> in_queue(n+1, false);

    pq.push(make_pair(0, 1));
    dist[1] = 0;
    in_queue[1] = true;

    while (!pq.empty())
    {
        int u = pq.top().second;
        in_queue[u] = false;
        pq.pop();

        for (auto el : adj[u]) 
        {
            int v = el.first;
            int cost = el.second;

            if (dist[u] + cost < dist[v])
            {
                dist[v] = dist[u] + cost;
                
                if (!in_queue[v])
                {
                    pq.push(make_pair(dist[v], v));
                    in_queue[v] = true;
                }
            }
        }
    }

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

    in.close();
    out.close();
}