#include<fstream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>


#define pb push_back
#define mp make_pair
#define f first
#define s second
#define NN 50009
#define INF 0x3f3f3f3f


using namespace std;
ofstream out("dijkstra.out");

int n , m ;

vector< pair < int , int  > > G[NN];
typedef vector < pair < int , int > >:: iterator IT;
vector<int>dist;


struct comp
{
    bool operator()
        ( int i , int j )
        {
            return dist[i] < dist[j];
        }
};

priority_queue< pair < int , int > >Q;

void read();
void Dijkstra( int root );
void wrs();

int main()
{
    read();
    Dijkstra(1);
    wrs();

    return 0;
}

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

    in >> n >> m;

    for( int x , y , cost ; m ; --m )
    {
        in >> x >> y >> cost;
        G[x].pb( mp ( y , cost ) );
    //    G[y].pb( mp ( x, cost ) );
    }
}

void Dijkstra( int root )
{
    dist.resize( n + 1 , INF );
    dist[ root ] = 0;
    Q.push( mp ( 0 , root  ) );

    int k ;
        while ( !Q.empty() )
        {
           int cost , nod;

           cost = -Q.top().f;
           nod = Q.top().s;

           Q.pop();

            for( int i = 0 ; i < G[nod].size(); ++i )
                if ( dist[ G[nod][i].f ] > cost + G[nod][i].s )
                {
                    dist[ G[nod][i].f ] = cost  + G[nod][i].s;
                    Q.push( mp ( -dist[ G[nod][i].f ] , G[nod][i].f ) );
                }
        }

}

void wrs()
{

    for( int i=2 ;i<=n ; i++)
        if ( dist[i] == INF )
            out << 0 << " " ;
            else
            out << dist[i] << " ";
}