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

using namespace std;

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

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

    list<pair<int, int> > *adj;
    adj = new list<pair<int, int> >[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));
    }

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

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

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

        for (auto it = adj[u].begin(); it != adj[u].end(); ++it)
        {
            int v = it->first;
            int cost = it->second;

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

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

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