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

struct nod
{
    int y,c;
};

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

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

int cauta()
{
    int nod_min = 1;
    long long cost_min = 100000000000;
    for(int i =1; i<=n; ++i)
        if(!fol[i] && cost[i])
            if(cost[i] < cost_min)
            {
                cost_min = cost[i];
                nod_min = i;
            }

    return nod_min;
}

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;

    while(k<n)
    {
        int nod_min = cauta();
        fol[nod_min] = 1;
        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;
        }
    }

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

    g<<"\n";


    return 0;
}