//Dijkstra O(nlog(n)) 100p  cu STL tipul SET (arbori de cautare  echilibrati )
// SET - Toate operatiile se fac in O(log(n))

#include <fstream>
#include <set>
#include <vector>
#define NMax 50100
#define inf 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, d[NMax]; vector<int> G[NMax], C[NMax];
set< pair<int, int> > T;
int i, x, y, costul;
void solve(void)
{
    int i, val, x;
    for(i = 2; i <= n; i++) d[i] = inf;
    T.insert( make_pair(0, 1) );
    while( T.size() > 0 )
    {
        val = (*T.begin()).first;
        x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
         {
            d[ G[x][i] ] = val + C[x][i];
            T.insert(make_pair(d[G[x][i]],G[x][i]));
         }
    }
}
int main(void)
{

    f>>n>>m;
    for(i = 1; i <=m ; i++)
    {
        f>>x>>y>>costul;
        G[x].push_back(y); C[x].push_back(costul);
    }
    solve();
    for ( int i = 2; i <= n; i++ )
        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
    g<<'\n';
    return 0;
}
////Dijkstra 40p  cu memorare graf cu liste de adiacenta O(n*n)clasic nu se incadreaza in timp
//#include <fstream>
//#define NMax 50003
//#define inf 1000000000
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//struct Nod
//{
//    int nod, cost;
//    Nod *next;
//};
//int n, m,x,y,costul;
//Nod *Vecin[NMax];
//int d[NMax], S[NMax];
//void adauga(int x, int y, int costul)
//{
//    Nod *q = new Nod;
//    q->nod = y;
//    q->cost = costul;
//    q->next = Vecin[x];
//    Vecin[x] = q;
//}
//
//void dijkstra()
//{
//    for ( int i = 2; i <= n; i++ ) d[i] = inf;
//    int mini, pmin = 0;
//    for ( int i = 1; i <= n; i++ )
//    {
//        mini = inf;
//        for ( int j = 1; j <= n; j++ )
//            if ( d[j] < mini && !S[j] )  {mini = d[j]; pmin = j;}
//
//        S[pmin] = 1;
//        Nod *t = Vecin[pmin];
//        while ( t )
//        {
//            if ( d[ t->nod ] > d[pmin] + t->cost )
//                       d[ t->nod ] = d[pmin] + t->cost;
//            t = t->next;
//        }
//    }
//}
//
//int main()
//{
//    f>>n>>m;
//    for ( int i = 1; i <= m; i++ )
//    {
//        f>>x>>y>>costul;
//        adauga(x, y, costul);
//    }
//    dijkstra();
//    for ( int i = 2; i <= n; i++ )
//        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
//    g<<'\n';
//
//    return 0;
//}