//Bellman Ford O(m*n) 100p
#include<fstream>
#include <deque>
#include<vector>
#define inf 1000000000
#define NMax 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct two{int urm,cost;};
vector <pair<int,int> >A[NMax];
deque <int> coada;
int i,m,n,a,b,c,nod,d[NMax];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
     {
        f>>a>>b>>c;
        A[a].push_back(make_pair(b,c));
     }
    for(i=1;i<=n;++i) d[i]=inf;
    coada.push_back(1);d[1]=0;
    while (!coada.empty())
     {
        nod=coada.front();coada.pop_front();

        for(i=0;i<A[nod].size();++i)
            if(d[nod]+A[nod][i].second < d[A[nod][i].first])
            {
                coada.push_back(A[nod][i].first);
                d[A[nod][i].first]=d[nod]+A[nod][i].second;
            }
     }
    for ( int i = 2; i <= n; i++ )
        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
    f.close();
    g.close();
}
////Bellman Ford O(m*n) 100p ??

////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 O(nlog(n)) 80p  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(1, 0) );//?
//    while( T.size() > 0 )
//    {
//        x = (*T.begin()).first;
//        val = (*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(G[x][i],d[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 O(nlog(n)) 100p  cu STL tipul SET (arbori de cautare  echilibrati )
// SET - Toate operatiile se fac in O(log(n))

////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;
//}