#include <fstream>
#include <vector>
using namespace std;
#define Inf 0x3f3f3f

ifstream is("1.in");
ofstream os("1.out");

int n, m;
struct edge{
    int u;
    int v;
    int cost;
};

vector<edge> E;
int d[50000];
int t[50000];

void Bf(int x);


int main()
{
    edge aux;
    is >> n >> m;
    E.resize(m+1);
    for(int i = 1; i <= m; ++i)
    {
        is >> aux.u >> aux.v >> aux.cost;
        E.push_back(aux);
    }
    Bf(1);
    for(int i = 2; i <= n; ++i)
        os << d[i] << ' ';
    is.close();
    os.close();
    return 0;
}

void Bf(int x)
{
    d[x] = 0;
    for(int i = 1; i <= n; ++i)
        if(i != x)
            d[i] = Inf;
    for(int i = 1; i < n; ++i)
    {
        for(vector<edge>::iterator it = E.begin(); it != E.end(); ++it)
        {
            int x = it->u;
            int y = it->v;
            int z = it->cost;
            if(d[y] > d[x] + z)
            {
                d[y] = d[x] + z;
                t[y] = x;
            }
        }
    }
    for(vector<edge>::iterator it = E.begin(); it != E.end(); ++it)
    {
        int x = it->u;
        int y = it->v;
        int z = it->cost;
        if(d[y] > d[x] + z)
            os << "neg";
    }
}