#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],poz;
vector < pair< int , int > > x[maxn];
deque <int> minim;
bool viz[maxn];

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=1 ; i<=n ; dist[i]=inf , i++ );
    for( i=0 ; i<x[nod].size() ; dist[x[nod][i].first]=x[nod][i].second , poz=search(x[nod][i].first) , viz[poz]=true , minim.insert( minim.begin() + poz , x[nod][i].first ) , i++ );
    while( minim.size() )
    {
        aux = minim[0];
        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;
                if( viz[x[aux][i].first] == false )
                {
                    poz=search( x[aux][i].first );
                    viz[poz]=true;
                    minim.insert( minim.begin() + poz ,x[aux][i].first );
                }
            }
        viz[aux]=false;
        minim.pop_front();
    }
}

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;
}