#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,vf_curent = 1;
bool viz[50001];
int tati[50001],distante[50001];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
vector<pair<int,int>>adiacenta[50001];
int main()
{
    f >> n >> m;
    for(int i = 1; i<=m; i++)
    {
        int A,B,C;
        f >> A >> B >> C;
        adiacenta[A].push_back({B,C});
    }
    for(int i = 1; i<=50000; i++)
        distante[i] = -1;
    distante[1] = 0;

    q.push({0,1});

    while(!q.empty())
    {
        int nod,cost;


        int cost_vf_curent = q.top().first;
        int vf_curent = q.top().second;

        q.pop();


        if(!viz[vf_curent])
        {
            viz[vf_curent] = 1;

            for(int i = 0; i<adiacenta[vf_curent].size(); i++)
            {

                int nod = adiacenta[vf_curent][i].first;
                int cost = adiacenta[vf_curent][i].second;
                if(distante[nod] > cost_vf_curent + cost || distante[nod] == -1)
                {
                    distante[nod] = cost_vf_curent + cost;
                    q.push({distante[nod],nod});
                    tati[nod] = vf_curent;
                }
            }
        }
    }
    for(int i = 2; i<=n; i++)
    {
        if(distante[i] == -1)
            g << "0 ";
        else
            g << distante[i]<< " ";
    }
}