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

    vector<list<pair<int, int> > > adj;
    adj.resize(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));
        // adj[y].push_back(make_pair(x, c));
    }

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

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

    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] == numeric_limits<int>::max())
            out << 0 << " ";
        else
            out << dist[i] << " ";
    }

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