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

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct muchie
{
    int cost;
    int dest;
};

vector <muchie> g[50003];
priority_queue < pair<int,int> > myHeap;
int m,n,i,x,y,c,d[50003],v[50003];

void Dijkstra()
{
    while(myHeap.empty()==0)
    {
        pair <int,int> cr=myHeap.top();
        myHeap.pop();
        int nod=cr.second;
        int costI=-cr.first;
        if(v[nod]==0)
        {
            v[nod]=1;
            d[nod]=costI;
            int lim=g[nod].size();
            for(i=0; i<lim; i++)
            {
                int vecin=g[nod][i].dest;
                int cost=g[nod][i].cost;
                if(cost+costI<d[vecin])
                {
                    d[vecin]=cost+costI;
                    myHeap.push( make_pair ((-1)*d[vecin],vecin));
                }
            }
        }
    }
}

int main()
{
    muchie a;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        a.cost=c;
        a.dest=y;
        g[x].push_back(a);

    }

    for(i=2; i<=50003; i++)
        d[i]=1234567890;
    myHeap.push(make_pair(0,1));
    Dijkstra();
    for(i=2; i<=n; i++)
        if(d[i]!=1234567890)
            out<<d[i]<<" ";
        else out<<0<" ";

    return 0;
}