#include <bits/stdc++.h>
#define NMAX 50005
#define INF 0x7fffffff

using namespace std;

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

using pi = pair<int, int>;

struct comp
{
    bool operator()(pi a, pi b)
    {
        return a.second > b.second;
    }
};

int n, m;
vector<pair<int, int>> v[NMAX];
vector<long long> dist(NMAX, INF);
priority_queue<pi, vector<pi>, comp> pq;

void graf()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
    }
}

int viz[NMAX];
void distante(int s = 1)
{
    pq.push(make_pair(1, 0));
    dist[s] = 0;
    while (!pq.empty())
    {
        int u = pq.top().first;
        viz[u] = 1;
        pq.pop();
        for (auto& i : v[u])
        {
            int v = i.first;
            int c = i.second;  //costul varfului de adaugat
            if (dist[v] > dist[u] + c)
            {  //daca distanta de la s la noul varf v este mai mare decat daca trecem prin varful ajutator u
                dist[v] = dist[u] + c;
                pq.push(make_pair(v, dist[v]));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (i != s) fout << dist[i] << " ";
}

int main()
{
    graf();
    distante();
}