#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#define INF 1<<30
#define VMAX 50000

using namespace std;

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

vector < pair<int, int> > adj[VMAX];
int V, E, x, y, cost;
bool vis[VMAX];
int d[VMAX];

struct compare
{
    bool operator() (int a, int b)
    {
        return d[a] > d[b];
    }
};

priority_queue <int, vector<int>, compare> q;

void Dijkstra(int src)
{
    int u, v;

    q.push(src);
    d[src] = 0;

    while (!q.empty())
    {
        u = q.top();
        q.pop();

        vis[u] = true;

        for (auto w:adj[u])
        {
             v = w.first;
             cost = w.second;
             if (!vis[v] && d[u] != INF && d[u] + cost < d[v])
             {
                 d[v] = d[u] + cost;
                 q.push(v);
             }
        }
    }
}

int main()
{
    fin >> V >> E;

    while (E--)
    {
        fin >> x >> y >> cost;
        adj[x - 1].push_back({y - 1, cost});
    }

    for (int i = 1; i < V; ++i)
        d[i] = INF;

    Dijkstra(0);

    for (int i = 1; i < V; ++i)
        d[i] == INF ? fout << 0 << " " : fout << d[i] << " ";

    fin.close();
    fout.close();
    return 0;

}