#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define Cmax 10000
#define Nmax 50005

vector <int> Lista[Cmax];
vector < pair<int,int> > G[Nmax];

int d[Nmax];

int N, M, S;

void sterge( int din, int ce )
{
    vector<int>::iterator it;

    for ( it = Lista[din].begin(); it != Lista[din].end(); ++it )
            if ( *it == ce )
            {
                Lista[din].erase( it );
                break;
            }
}

void Dijkstra()
{
    S = 1;

    Lista[0].push_back( S );

    for ( int i = 1; i <= N; ++i )
    {
        Lista[Cmax].push_back( i );
        d[i] = Cmax;
    }

    d[S] = 0;

    for ( unsigned i = 0; i <= Cmax; ++i )
            for ( unsigned j = 0; j < Lista[i].size(); ++j )
            {
                int nod = Lista[i][j];

                for ( unsigned l = 0; l < G[nod].size(); ++l )
                        if ( d[ G[nod][l].first ] > d[nod] + G[nod][l].second )
                        {
                            sterge( d[ G[nod][l].first ], G[nod][l].first );
                            d[G[nod][l].first] = d[nod] + G[nod][l].second;
                            Lista[ d[G[nod][l].first] ].push_back( G[nod][l].first );
                        }
            }
}

void read()
{
    ifstream f("dijkstra.in");

    f >> N >> M;

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b >> c;

        G[a].push_back( make_pair(b,c) );
    }

    f.close();
}

void print()
{
    ofstream g("dijkstra.out");

    for ( int i = 2; i <= N; ++i )
            if ( d[i] == Cmax )
                g << 0 << " ";
            else
                g << d[i] << " ";

    g.close();
}

int main()
{
    read();
    Dijkstra();
    print();

    return 0;
}