#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
const int VMAX = 50000, INF = 1 << 30;
struct path
{
    int nextNode, weight;
};
struct node
{
    int curr, totalWeight;
};
struct cmp
{
    public : bool operator()(const node a, const node b)
    {
        return (a.totalWeight > b.totalWeight);
    };
};


int minWeight[VMAX + 1];
vector<path> lists[VMAX + 1];
priority_queue<node, vector<node>, cmp> pq;

int main()
{
    int n, m, i, w, l, r;
    node currNode;
    FILE *fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        minWeight[i] = INF;
    for (i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d%d", &l, &r, &w);
        lists[l].push_back({r, w});
    }
    fclose(fin);

    pq.push({1, 0});
    while (!pq.empty())
    {
        currNode = pq.top();
        pq.pop();
        if (currNode.totalWeight < minWeight[currNode.curr])
        {
            minWeight[currNode.curr] = currNode.totalWeight;
            for (i = 0; i < lists[currNode.curr].size(); i++)
                pq.push({lists[currNode.curr][i].nextNode, lists[currNode.curr][i].weight + currNode.totalWeight});
        }
    }

    FILE *fout = fopen("dijkstra.out", "w");
    for (i = 2; i <= n; i++)
    {
        if (minWeight[i] == INF)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", minWeight[i]);
    }
    fclose(fout);
    return 0;
}