#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define alot 2e9

using namespace std;
int n, m;
class nod{
public:
    int id;
    vector <pair <int, int> > vecini ;       //se va inlocui cu lista
};
class cmp{
public:
    bool operator () (pair <nod, int> p1, pair <nod, int> p2)
    {
    return p1.second > p2.second;
    }

};

priority_queue <pair <nod, int>,
                vector<pair <nod, int> >,
                cmp> Q;

vector <nod> G (50001);
vector <int> dist (50001);
//vector <bool> vizitat (50001);
bitset <50001> vizitat;
int main()
{
    int i, x, y, z;
    ifstream g ("dijkstra.in");
    ofstream h ("dijkstra.out");
    nod curr;
    g>>n>>m;
    //G.resize(n+1);
    //vizitat.resize(n+1);
    //dist.resize(n+1);

    for(i=0;i<m;i++)
    {
        g>>x>>y>>z;
        G[x].vecini.push_back(make_pair(y, z));
        G[x].id = x;

    }
    dist[1]=0;
    for(i=2;i<=n;++i)
        dist[i]=alot;
    Q.push(make_pair(G[1], dist[1]));
    while (!Q.empty())
    {
        /*for (i=1;i<=n;++i)
            cout<<dist[i]<<" ";
        cout<<endl;*/
        //minim=alot;
        curr = Q.top().first;
        Q.pop();
        //if(dist[curr.id]==alot)
          //  break;
        if(vizitat[curr.id])
                continue;
        /*for(i=1;i<=n;++i)
            if(minim > dist[i] && !vizitat[i])
            {
                minim = dist[i];
                minpoz = i;
            }
        if (minim == alot)      //toate nodurile sunt unreachable
            break;
        vizitat[minpoz]=1;*/
        vizitat[curr.id]=1;
        for (i = 0; i<curr.vecini.end() - curr.vecini.begin();++i)
            if(dist[curr.id] + curr.vecini[i].second < dist[curr.vecini[i].first])
            {
                dist[curr.vecini[i].first] = dist[curr.id] + curr.vecini[i].second;
                Q.push(make_pair(G[curr.vecini[i].first], dist[curr.vecini[i].first]));
            }


    }
    for (i=2;i<=n;++i)
    {
        if(dist[i]==alot)
            h<<"0 ";
        else
            h<<dist[i]<<" ";
    }
}