#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <climits>
using namespace std;

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

queue<pair<int, int> > Q;
int cost[50005], viz[50005], n, m;

struct vecin
{
    int c, info;
    vecin(int c, int info)
    {
        this->c = c;
        this->info = info;
    }
};
vector<vecin> nod[50005];

void citire()
{
    f>>n>>m;
    int x, y, c;
    for(int i = 0; i<m; ++i)
    {
        f>>x>>y>>c;
        nod[x].push_back(vecin(c, y));
    }
}

bool bellman()
{
    Q.push({1, 0});
    while(!Q.empty())
    {
        int currNod = Q.front().first;
        int len = Q.front().second;
        viz[currNod] = 0;
        Q.pop();
        cout << currNod << " " << len << "\n";
        if(len == n+6)
        {
            return false;
        }
        for(int i = 0; i<nod[currNod].size(); ++i)
        {
            if(cost[nod[currNod][i].info] > cost[currNod] + nod[currNod][i].c)
            {
                if(viz[nod[currNod][i].info] == 0)
                    Q.push({nod[currNod][i].info, len+1});
                cost[nod[currNod][i].info] = cost[currNod] + nod[currNod][i].c;
                viz[nod[currNod][i].info] = 1;
            }
        }
    }
    return true;
}

int main()
{
    memset(cost, 11, sizeof(cost));
    cost[1] = 0;
    citire();
    if(bellman() == false)
        g<<"Ciclu negativ!";
    else
        for(int i = 2; i<=n; ++i)
        {
            g<<cost[i]<<" ";
        }
    return 0;
}