#include <bits/stdc++.h>
using namespace std;

#define INF (1<<30)

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

int n, m;
int d[50001];
vector<pair<int,int>> v[50001];

priority_queue<
    pair<int,int>,
    vector<pair<int,int>>,
    greater<pair<int,int>>
> q;

void dijkstra(int start)
{
    for(int i = 1; i <= n; i++)
        d[i] = INF;

    d[start] = 0;
    q.push({0, start});

    while(!q.empty())
    {
        auto [dist, nod] = q.top();
        q.pop();

        // Dacă distanța este veche, ignorăm
        if(dist != d[nod]) continue;

        for(auto &e : v[nod])
        {
            int vecin = e.first;
            int cost = e.second;

            if(dist + cost < d[vecin])
            {
                d[vecin] = dist + cost;
                q.push({d[vecin], vecin});
            }
        }
    }
}

int main()
{
    fin >> n >> m;

    int x, y, z;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++)
    {
        if(d[i] == INF) fout << 0 << " ";
        else fout << d[i] << " ";
    }

    return 0;
}