#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

struct nod
{
    int y,c;
};

struct fpq
{
    int idx;
    long long cost;

    fpq(int id, int cst)
    {
        idx = id;
        cost = cst;
    }

    bool operator<(const fpq b) const
    {
        return b.cost < cost;
    }
};

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

vector<nod> a[50100];
int n,m;
long long cost[50010];
int fol[50010];
priority_queue<fpq> pq;

int main()
{
    f>>n>>m;
    for(int i =1; i<=m; ++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        nod t;
        t.y = y;
        t.c = c;
        a[x].push_back(t);
    }

    int sursa= 1;
    cost[sursa] = 1;
    int k = 0;

    pq.push(fpq(1,1));

    while(k<n)
    {
        fpq t = pq.top();
        pq.pop();
        int nod_min = t.idx;
        k++;

        for(int j = 0; j<a[nod_min].size(); ++j)
        {
            int vec=  a[nod_min][j].y;

            long long cost_vec = cost[nod_min] + a[nod_min][j].c;

            if(cost_vec < cost[vec] || !cost[vec])
            {
                cost[vec] = cost_vec;
                pq.push(fpq(vec, cost_vec));
            }
        }
    }

    for(int i = 2; i<=n; ++i)
    if (!cost[i])
        g<<"0 ";
    else
        g<<cost[i]-1<<" ";

    g<<"\n";


    return 0;
}