#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
const int maxn=50005,inf=250000009;
int n,m,i,aux,a,b,c,dist[maxn];
vector < pair< int , int > > x[maxn];
deque <int> minim;

void read()
{
    fscanf(f,"%d%d",&n,&m);
    for( i=1 ; i<=m ; fscanf(f,"%d%d%d",&a,&b,&c) , x[a].push_back(make_pair(b,c)) , i++ );
}

int search(int nod)
{
    int l=0,r=minim.size(),mid;
    if(r)
    {
        while(l<r)
        {
            mid=(l+r)/2;
            if( dist[nod] > dist[ minim[mid] ] )
                l=mid+1;
            else
                r=mid;
        }
        if( minim.size() > l && dist[nod] > dist[ minim[l] ] )
            l++;
    }
    return l;
}

void dijkstra(int nod)
{
    for( i=2 ; i<=n ; dist[i]=inf , i++ );
    minim.push_back(1);
    while( minim.size() )
    {
        aux = minim[0];
        minim.pop_front();
        for( i=0 ; i < x[aux].size() ; i++ )
            if( dist[ x[aux][i].first ] > dist[ aux ] + x[aux][i].second )
            {
                dist[ x[aux][i].first ] = dist[ aux ] + x[aux][i].second;
                minim.insert( minim.begin() + search( x[aux][i].first ) ,x[aux][i].first );
            }
    }
}

void write()
{
    for( i=2 ; i<=n ; i++ )
        if( dist[i] < inf )
            fprintf(g,"%d ",dist[i]);
        else
            fprintf(g,"0 ");
    fprintf(g,"\n");
}

int main()
{
    read();
    dijkstra(1);
    write();
    return 0;
}