#include <iostream>
#include <stdio.h>
#include <vector>
#define Max 999999999
#define NMax 50099
using namespace std;
vector< pair <int,int > > c[NMax];
int uz[NMax],d[NMax],N,M,Min=Max,poz;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

void Initializare()
{
    for(int i=2;i<=N;i++)
        d[i]=Max;
}

void Citire()
{
    int x,y,z;
    fscanf(f,"%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        c[x].push_back(make_pair(y,z));
    }
}

void Dijkstra()
{
    Initializare();
    for(int i=1;i<=N;i++)
    {
        Min=Max;
        for(int j=1;j<=N;j++)
        {
            if(Min>d[j] && uz[j]==0)
                Min=d[j],poz=j;
        }
        uz[poz]=1;
        for(int j=0;j<c[poz].size();j++)
        {
            if(d[c[poz][j].first]>d[poz]+c[poz][j].second)
            {
                d[c[poz][j].first] = d[poz] + c[poz][j].second;
            }
        }
    }
}

void Afisare()
{
    for(int i=2;i<=N;i++)
        if(d[i]==Max)
        fprintf(g,"0 ");
        else
        fprintf(g,"%d ",d[i]);
}

int main()
{
    Citire();
    Dijkstra();
    Afisare();
}