#include<fstream>
#include<vector>
#define INFINIT 0x3f3f3f
#define nmax 50002
#define mmax 250001
using namespace std;
typedef struct
{
    int cost;
    unsigned short int a;
    unsigned short int b;
} muchie;
muchie muchii[mmax];
unsigned int noduri[nmax];
unsigned short int n;
unsigned int m;
void citire()
{
    ifstream f("dijkstra.in",fstream::in);
    f>>n>>m;
    for(unsigned int i=1; i<=m; i++)
        f>>muchii[i].a>>muchii[i].b>>muchii[i].cost;
    f.close();
}
void tipar()
{
    ofstream g("dijkstra.out",fstream::out);
    for(unsigned short int i=2; i<=n; i++)
        if(noduri[i]<INFINIT)
            g<<noduri[i]<<" ";
        else
            g<<"0 ";
    g.close();
}
void BF()
{
    short int q=1;
    noduri[1]=0;
    for(unsigned short int i=2;i<=n; i++)
        noduri[i]=INFINIT;
    for(unsigned short int i=1; i<=n &&q; i++)
    {  q=0;
        for(unsigned int j=1; j<=m; j++)
            if((noduri[muchii[j].a]+muchii[j].cost)<noduri[muchii[j].b])
            {
                noduri[muchii[j].b]=noduri[muchii[j].a]+muchii[j].cost;
                q=1;
            }
    }
}
int main()
{
    citire();
    BF();
    tipar();
    return 0;
}