#include <iostream>
#include <fstream>
#define PII pair<int,int>
#define inf 1e9
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector <PII> v[50005];
priority_queue <PII, vector<PII>, greater<PII> > h;
int n,m,d[50005],c[50005];
void djk(int ns)
{
    int nod,vecin,cost;
    for(int i=1;i<=n;i++)
        d[i]=inf;
        d[ns]=0;
        h.push({0,ns});
    while(!h.empty())
    {
        nod=h.top().second;
        cost=h.top().first;
        h.pop();
        if(d[nod]!=cost) continue;
            for(int i=0;i<v[nod].size();i++)
            {
                vecin=v[nod][i].second;
                cost=v[nod][i].first;
                if(d[nod]+cost<d[vecin])
                {
                    d[vecin]=d[nod]+cost;
                    h.push({d[vecin],vecin});
                    c[vecin]++;
                    if(c[vecin]==n)
{
    g<<"Ciclu negativ!";
    exit(0);
}
                }
            }


    }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        v[a].push_back({c,b});
    }
    djk(1);
    for(int i=2;i<=n;i++)
        if(d[i]==inf) out<<0<<" ";
    else out<<d[i]<<" ";
    return 0;
}