#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(); // u are, deja, distanta potrivita
        q.pop();

        if (!vis[u])
        {
            vis[u] = true;
            for (auto w:adj[u])
            {
                 v = w.first;
                 cost = w.second;
                 if (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)
        fout << (d[i] == INF ? 0 : d[i]) << " ";

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

}