#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>
#define N_MAX 50001
using namespace std;

int main()
{
    int n,m;
    ifstream f("dijkstra.in");
    f>>n>>m;
    int i,nod,vecin,cost,distanta[N_MAX];
    bool vizitat[N_MAX];
    vector<pair <int,int> > vecini[N_MAX];
    priority_queue< pair <int,int>, vector< pair <int,int> >, greater< pair <int,int> > > que;

    for (i = 0;i < m;i++)
    {
        f>>nod>>vecin>>cost;
        vecini[nod-1].push_back(make_pair(vecin-1,cost));
    }
    f.close();

    for (i = 1;i < n;i++)
    {
        distanta[i] = INT_MAX;
        vizitat[i] = false;
    }
    que.push(make_pair(0,0));

    while (!que.empty())
    {
        nod=que.top().second;
        que.pop();
        vizitat[nod]=true;
        for (vector<pair <int,int> >::iterator it = vecini[nod].begin();it != vecini[nod].end();++it)
            if (vizitat[it->first] == false && distanta[it->first] > distanta[nod] + it->second)
            {
                distanta[it->first] = distanta[nod] + it->second;
                que.push(make_pair(distanta[it->first],it->first));
            }
    }

    ofstream g("dijkstra.out");
    for (i = 1;i < n;i++)
        if(distanta[i] == INT_MAX)
            g<<"0 ";
        else
            g<<distanta[i]<<" ";
    g.close();
    return 0;
}