#define MAX_N 50000

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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int start = 1;

struct edge
{
    int node, cost;

    bool operator> (const edge& other) const
    { return cost > other.cost; }
};

int n, m, d[MAX_N + 1];
vector<edge> g[MAX_N + 1];

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({ y, c });
    }
    for (int i = 1; i <= n; ++i)
    {
        d[i] = -1;
    }
    priority_queue<edge, vector<edge>, greater<edge>> q;
    q.push({ start, 0 });
    while (!q.empty())
    {
        edge e  = q.top();
        q.pop();
        if (d[e.node] != -1)
            continue;
        d[e.node] = e.cost;
        for (edge next : g[e.node])
        {
            q.push({ next.node, e.cost + next.cost });
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        fout << ((d[i] == -1) ? 0 : d[i]) << ' ';
    }
    fin.close();
    fout.close();
    return 0;
}