#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];
struct comp
{
    bool operator () (const int &x, const int &y)
    {
        return (dist[x] > dist[y]);
    }
};

priority_queue <int , vector < int > , comp > 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++ );
}

void dijkstra(int nod)
{
    for( i=2 ; i<=n ; dist[i]=inf , i++ );
    minim.push(1);
    while( minim.size() )
    {
        aux = minim.top();
        minim.pop();
        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.push(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;
}