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

#define DMAX 50010

using namespace std;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;
    scanf("%d %d\n", &n, &m);

    list<pair<int, int> > adj[DMAX];

    int x, y, c;
    for (int i = 0; i < m; ++i) 
    {
        scanf("%d %d %d\n", &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> >, greater<pair<int, int> > > pq;

    int dist[DMAX];
    for (int i = 1; i <= n; ++i)
        dist[i] = MAX;

    bool in_heap[DMAX];
    for (int i = 1; i <= n; ++i)
        in_heap[i] = false;

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

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

        if (dist[u] != cu)
            continue;

        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 ";
            printf("0 ");
        else
            // out << dist[i] << " ";
            printf("%d ", dist[i]);
    }

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