#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define infinit 123456789

using namespace std;

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

int N, M, S, d[100009];

struct Nod{
     int nod, cost;

     bool operator < (const Nod&e) const
     {
         return (cost > e.cost);
     }
};

vector <Nod> L[50005];

void Citire()
{
    int i, j, x, y, cost;
    Nod w;
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y >> cost;
        w.nod = y;  w.cost = cost;
        L[x].push_back(w);
    }
    for (i=1; i<=N; i++)
        d[i] = infinit;
}

void Djikstra()
{
    int i, k, cost, costt;
    priority_queue <Nod> q;
    d[1] = 0;
    Nod w, w1;
    w.nod = 1; w.cost = 0;
    q.push(w);

    while (!q.empty())
    {
        w = q.top();
        k = w.nod;
        cost = w.cost;
        q.pop();

        for (int j=0; j<L[k].size(); j++)
        {
            i = L[k][j].nod;  costt = L[k][j].cost;

            if (d[i] == infinit || d[i] > d[k] + costt)
            {
                d[i] = d[k] + costt;
                w1.nod = i; w1.cost = d[i];
                q.push(w1);
            }
        }
    }
}

void Afisare()
{
    int i;
    for (i=2; i<=N; i++)
       if (d[i] != infinit)
        fout << d[i] << " ";
       else
        fout << "-1 ";
    fout << "\n";
}

int main ()
{
    Citire();
    Djikstra();
    Afisare();
    fin.close();
    fout.close();
    return 0;
}