#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define inf 1e9
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
vector < pair <int,int> > v[nmax] ;
priority_queue < pair <int , int> , vector <pair <int,int> > , greater <pair <int,int> > > h;
int N , M , i,j , x ,y , cost , nod ;
int d[nmax];
bool viz[nmax] ;
int main()
{
    f >> N >> M ;
    for (i = 1 ; i <= M ; ++i)
    {
            f >> x >> y >> cost;
            v[x].push_back(make_pair(cost,y));
    }
    for (i = 1 ; i <= N ; i ++)
        d[i] = inf ;
    d[1]=0;
    h.push(make_pair(0,1));
    while (!h.empty())
{
        nod = h.top().second;
        h.pop();
        if (!viz[nod])
            for (i = 0 ; i < v[nod].size() ; ++ i)
            {
                if (d[nod] + v[nod][i].first < d[v[nod][i].second])
                {
                    d[v[nod][i].second] = d[nod] + v[nod][i].first;
                    h.push(make_pair(d[v[nod][i].first] , v[nod][i].second) );
                }
            }
            viz[nod] = true;

}
        for (i = 2 ; i <= N ; i ++)
            if (d[i] == inf) g << 0 << " ";
        else g << d[i] << " " ;
        return 0;
}