#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

const int inf = 2e8;

int n , m;

bool nwc = false;

int dist[50005];
int previous[50005];

struct edge
{
    int x , d;
};
vector<edge>edges[50005];
priority_queue<pair<int,int> > pq;
deque<int>d;
bitset<50005>f;


void refresh()
{
    for(int i = 1; i <= n; ++i)
        dist[i] = inf , previous[i] = 0;

}

void dijkstra(int k)
{
    refresh();
    pq.push({0 , k});
    f[k] = 1;
    dist[k] = 0;
    while(!pq.empty())
    {
        int node = pq.top().second;
        f[node] = 0;
        pq.pop();
        for(auto &i:edges[node])
            if(dist[i.x] > dist[node] + i.d)
            {
                dist[i.x] = dist[node] + i.d;
                previous[i.x] = node;
                if(f[i.x]==0)
                f[i.x] = 1 , pq.push({-dist[i.x] , i.x});
            }
    }
}

void BellmanFord(int k)
{
    refresh();
    dist[k] = 0;
    for(int i = 1; i < n; i++)
        for(int u = 1; u <= n; u++)
            for(auto &v:edges[u])
                if(dist[v.x] > dist[u] + v.d)
                {
                    dist[v.x] = dist[u] + v.d;
                    previous[v.x] = u;
                }

    for(int u = 1; u <= n; u++)
        for(auto &v:edges[u])
            if(dist[v.x] > dist[u] + v.d)
                nwc = true;///negative-weight cycle
}




void DEsopoPape(int k) /// aka pepe
{
    ///m[node] == 0 -> out of deque, calculated
    ///m[node] == 1 -> in deque , high priority
    ///m[node] == 2 -> never calculated, low priority
    refresh();
    d.push_back(k);
    vector<int>m(n + 1 , 2);
    dist[k] = 0;
    while(!d.empty())
    {
        int node = d.front();
        m[node] = 0;
        d.pop_front();
        for(auto &i:edges[node])
            if(dist[i.x] > dist[node] + i.d)
            {
                dist[i.x] = dist[node] + i.d;
                previous[i.x] = node;
                if(m[i.x] == 2)
                {
                    m[i.x] = 1;
                    d.push_back(i.x);
                }
                else
                if(m[i.x] == 0)
                {
                    m[i.x] = 1;
                    d.push_front(i.x);
                }
            }
    }
}

int main()
{
    int a , b , d;
    in >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        in >> a >> b >> d;
        edges[a].push_back({b , d});
        //edges[b].push_back({a , d});
    }
    dijkstra(1);
    if(nwc == true)
        {out << "negative-weight cycle";return 0;}
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] == inf)
            out << 0 << " ";
        else
            out << dist[i] << " ";
    }
    return 0;
}