#include<fstream>
#include<queue>
using namespace std;
const int MAXN=50002;
const int INF=1<<30;
int n,m,d[MAXN],source=1;
typedef pair<int,int> edge;
vector<edge> G[MAXN];
queue<int> Q;
void read()
{
    int i,x,y,c;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    fin.close();
}

bool bellman_ford(int src)
{
    int i,u,v,w;
    for (i=1; i<=n; d[i]=INF, ++i);
    d[src]=0;

    for (i=1; i<=n-1; ++i)
    {
        Q.push(src);
        while (!Q.empty())
        {
            u=Q.front();
            Q.pop();
            for (vector<edge>::iterator it=G[u].begin(); it!=G[u].end(); ++it)
            {
                v=(*it).first;
                w=(*it).second;
                if (d[v]>d[u]+w)
                {
                    d[v]=d[u]+w;
                    Q.push(v);
                }
            }
        }
    }

    Q.push(src);
    while (!Q.empty())
    {
        u=Q.front();
        Q.pop();
        for (vector<edge>::iterator it=G[u].begin(); it!=G[u].end(); ++it)
        {
            v=(*it).first;
            w=(*it).second;
            if (d[v]>d[u]+w)
                return false;
            if (d[v]==d[u]+w)
                Q.push(v);
        }
    }
    return true;
}
void write(int src)
{
    ofstream fout("bellmanford.out");
    if (bellman_ford(src))
    {
        for (int i=1; i<=n; ++i)
        {
            if (i==src) continue;
            fout<<d[i]<<' ';
        }
    }
    else
        fout<<"Ciclu negativ!\n";
    fout.close();
}
int main()
{
    read();
    write(source);
    return 0;
}