/*
 * Simple BellmanFord in O(N*M)
 * Algoritmul ia fiecare muchie de N ori.
 * Drumul minim va trece prin maxim N noduri.(altfel avem ciclu negativ)
 * De fiecare data cand luam muchiile odata ne apropiem cu on nod de acest drum minim.
 */

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 50000;
const int MMAX = 250000;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n; int m;

vector< pair<int, int> > g[NMAX];

class Edge {

public:
	int x; int y; int cost;

	Edge(){
		this->x = 0;
		this->y = 0;
		this->cost = 0;
	}

	Edge(int x, int y, int cost) {
		this->x = x;
		this->y = y;
		this->cost = cost;
	}
};

vector<Edge> edges;


void read() {

	fin >> n >> m;

	for(int i = 1; i <= m ; ++i) {

		int x; int y; int cost;
		fin >> x >> y >> cost;
		g[x].push_back({y, cost});
		edges.push_back(Edge(x, y, cost));
	}
}

void bellmanFord() {



}

int main() {

	read();

	bellmanFord();

	return 0;
}