#include <fstream>
#include <queue>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

struct minHeapOrder
{
    bool operator()(const pair<int, int> &a, const pair<int, int> &b)
    {
        return a.second > b.second;
    }
};

int main()
{
    int i, N, M, A, B, C;
    ifstream f("dijkstra.in");
    f >> N >> M;
    vector<pair<int, int>> adjList[N + 1];

    for (i = 1; i <= M; i++)
    {
        f >> A >> B >> C;
        adjList[A].push_back(make_pair(B, C));
    }
    f.close();

    int dist[N + 1];
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, minHeapOrder> pq;
    pq.push(make_pair(1, dist[1]));

    pair<int, int> x;
    pair<int, int> neighbor;
    while (!pq.empty())
    {
        x = pq.top(), pq.pop();
        for (i = 0; i < adjList[x.first].size(); i++)
        {
            neighbor = adjList[x.first][i];
            if (dist[neighbor.first] > dist[x.first] + neighbor.second)
            {
                dist[neighbor.first] = dist[x.first] + neighbor.second;
                pq.push(make_pair(neighbor.first, dist[neighbor.first]));
            }
        }
    }

    ofstream g("dijkstra.out");
    for (i = 2; i <= N; i++)
    {
        if (dist[i] == INF)
            g << 0;
        else
            g << dist[i];
        g << ' ';
    }
    g.close();


    return 0;
}