#include <fstream>
#include <queue>
#include <vector>
#define y first
#define c second
#define NMAX 50003
using namespace std;

vector< pair<int, int> > G[NMAX];
queue<int> Q;
int inQ[NMAX], D[NMAX], nr[NMAX], n, m;
const int inf=2000000000;

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

bool Bell()
{   int i;
    for (i=1; i<=n; ++i)
        D[i]=inf;
    D[1]=0;
    Q.push(1);
    inQ[1]=1;
    while (!Q.empty())
    {   int nod=Q.front();
        Q.pop();
        inQ[nod]=0;
        for (i=0; i<G[nod].size(); ++i)
        {   int k=G[nod][i].y, cost=G[nod][i].c;
            if (D[k]>D[nod]+cost)
            {   D[k]=D[nod]+cost;
                nr[k]++;
                if (nr[k]==n)
                    return 0;
                if (!inQ[k])
                {   Q.push(k);
                    inQ[k]=1;
                }
            }
        }
    }
    return 1;
}

int main()
{   f>>n>>m;
    int a, b, c;
    for (; m; --m)
    {   f>>a>>b>>c;
        G[a].push_back(make_pair(b, c));
    }
    if (!Bell())
        g<<"Exista un ciclu negativ";
    else
        for (int i=2; i<=n; ++i)
            g<<(D[i]!=inf)*D[i]<<' ';
    return 0;
}