#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define Nmax 50005
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

vector <pair<int,int>> liste[Nmax]; //.first= costul muchie,.second e nodul
int n,m;

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

void Dijkstra ()
{
    set<pair<int,int>> distante;
    int t[Nmax]={0},i;
    int d[Nmax];
    int viz[Nmax];
    const int inf=200000000;
    for (i=2;i<=n;i++)
    {distante.insert({inf,i});//adaug in distante, fiecare pereche de tipul (d[i],i)
        d[i]=inf;
        t[i]=inf;
    }
    d[1]=0;
    distante.insert({0,1});
    for (i=1;i<=n;i++)
    {
       pair<int,int> nod=*(distante.begin());
       distante.erase(distante.begin());
        viz[nod.second]=1;
        for (pair<int,int> aux:liste[nod.second])
        {
            if (d[nod.second]+aux.first<d[aux.second])
            {
                distante.erase({d[aux.second],aux.second});
                d[aux.second]=d[nod.second]+aux.first;
                distante.insert({d[aux.second],aux.second});
                t[aux.second]=nod.second;
            }
        }

    }
    for (i=2;i<=n;i++)
        if (d[i]!=inf)
        fout<<d[i]<<" ";
else fout<<0<<" ";

}

int main()
{
    Citire();
    Dijkstra();
    return 0;
}