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

struct nod
{
    int y,c;
};

struct fpq
{
    int idx;
    long long cost;

    fpq(int id, long long 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> G[50100];
int n,m;
long long cost[50010];
int fol[50010];
priority_queue<fpq> pq;
nod t;

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

    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<G[nod_min].size(); ++j)
        {
            int vec=  G[nod_min][j].y;

            long long cost_vec = cost[nod_min] + G[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;
}