#include <bits/stdc++.h>

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

struct comp
{
    bool operator () (const pair<int, int> a, const pair<int, int> b)
    {
        return a.first > b.first;
    }
};

const int maxN = 5e4 + 5 ;
priority_queue< pair<int, int>, vector<pair<int, int> >, comp> coada;
vector<pair<int,int>> g[maxN];
int viz[maxN];
int dist[maxN];

int main()
{

    int n, m;
    fin >> n >> m;

    while(m--)
    {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].push_back({y,z});
    }

    for(int i=1; i<=n; i++)
        dist[i] = INT_MAX;


    viz[1] = 1;
    dist[1] = 0;
    coada.push({0,1});

    while(!coada.empty())
    {
        int nod = coada.top().second;
        coada.pop();
        viz[nod] = 1;

        for(auto it: g[nod])
        {
            if(viz[it.first] == false)
            {
                 if(dist[nod] + it.second < dist[it.first]){
                       dist[it.first] = dist[nod] + it.second;
                       coada.push({dist[it.first], it.first});
                 }
            }
        }

    }
    for (int i = 2; i <= n; i++)
        fout << (dist[i] == INT_MAX ? 0 : dist[i] )<< " ";
}