#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define inf 0x3F3F3F3F
#define nrmax 50001
#define nod first
#define cost second
#define pb push_back
#define mp make_pair
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n , m ;
vector < pair < int , int > > G[nrmax];
int d[nrmax];
bool used[nrmax];

void citire_date()
{
    f >> n >> m ;
    for ( ; m-- ; )
    {
        int x,y,z;
        f >> x >> y >> z;
        G[x].pb(mp(y,z));
    }
}

void bellman_ford()
{
    queue < int > Q;
    memset(d,inf,sizeof d);
    d[1] = 0;
    Q.push(1);
    while ( !Q.empty() )
    {
        int x = Q.front();
        Q.pop();
        used[x] = false;
        for ( vector < pair < int , int > > ::iterator j = G[x].begin(); j != G[x].end(); j++ )
        {
            if ( d[(*j).nod] > d[x] + (*j).cost )
            {
                d[(*j).nod] = d[x] + (*j).cost ;
                if ( !used[(*j).nod] )
                {
                    used[(*j).nod] = true;
                    Q.push((*j).nod);
                }
            }
        }
    }
    for ( int i = 2; i <= n ; i++ )
        g << d[i] << " " ;
}


int main()
{
    citire_date();
    bellman_ford();
    return 0;
}