#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#define N 50005

using namespace std;

ifstream fin( "dijkstra.in" );
ofstream fout( "dijkstra.out" );

/*struct mzg
{
    int a, b, c;

    bool operator < ( const mzg &A ) const
    {
        return ( b < A.b || b == A.b && c < A.c );
    }
};*/

const int inf = 1 << 30;
typedef pair < int, int > pii;

int n, m;
vector <int> Ad[N];
vector <int> Cost[N];

bool in_h[N];
int d[N];

void read()
{
    int i, x, y, dist;

    fin >> n >> m;

    for ( i = 1; i <= m; ++i )
    {
        fin >> x >> y >> dist;

        Ad[x].push_back( y );
        Cost[x].push_back( dist );
    }

    fin.close();
}

void solve()
{
    int i, w;
    priority_queue < pii, vector <pii>, greater <pii> > Heap;

    for ( i = 1; i <= n; ++i )
         d[i] = inf;

    d[1] = 0;

    Heap.push( make_pair( 0, 1 ) );

    int nod, d_curent;

    while ( !Heap.empty() )
    {
        nod = Heap.top().second; Heap.pop();

        if ( in_h[nod] ) continue;
        else in_h[nod] = 1;

        for ( i = 0; i < Ad[nod].size(); ++i )
        {
            w = Ad[nod][i];

            if ( d[nod] + Cost[nod][i] < d[w] )
            {
                d[w] = d[nod] + Cost[nod][i];

                Heap.push( make_pair( d[w], w ) );
            }
        }
    }

    for ( i = 2; i <= n; ++i )
         if ( d[i] != inf )
             fout << d[i] << ' ';
         else fout << 0 << ' ';
}

int main()
{
    read();
    solve();

    fout.close();

    return 0;
}