#include <bits/stdc++.h>

#define llg     long long

#define MAXN    50005
#define INF     4e18

int N, M, times[MAXN];
llg dist[MAXN];
std::vector <std::pair <int, int>> ADC[MAXN];
inline void addEdge(int u, int v, int w) {
    ADC[u].push_back({v, w});
}
std::queue <int> queue;
bool inQueue[MAXN], bNaspa;
void bellmanFord() {
    for (int i=1; i<=N; ++i) dist[i] = INF;
    queue.push(1); dist[1] = 0;
    inQueue[1] = true;
    while (!queue.empty()) {
        int front = queue.front();
        queue.pop();
        inQueue[front] = false;
        std::cout << front << ' ' << dist[front] << '\n';
        ++  times[front];
        if (times[front] >= N+1) { bNaspa = true; return; }
        for (auto &it:ADC[front])
            if (dist[it.first] > dist[front] + it.second) {
                dist[it.first] = dist[front] + it.second;
                if (!inQueue[it.first]) inQueue[it.first] = true, queue.push(it.first);
            }
    }
}

#define FILENAME    std::string("bellmanford")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int32_t main()
{
    input >> N >> M;
    for (int i=1, u, v, w; i<=M; ++i)
        input >> u >> v >> w, addEdge(u, v, w);
    bellmanFord();
    if (bNaspa) output << "Ciclu negativ!";
    else {
        for (int i=2; i<=N; ++i)
            output << dist[i] << ' ';
    }

    return 0;
}