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

using namespace std;

const int MAX = 50050;
const int INF = 1 << 30;

list<pair<int, int> > adj[MAX];
vector<int> dist(MAX, INF);
bool in_queue[MAX];

struct cmp {
    bool operator() (pair<int, int> a, pair<int, int> b)
    {
        return a.first < b.first;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;

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

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


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

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

    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();
}