#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int inf = 0x3f3f3f3f;

int g[1024][1024];
int ds[1024], ps[1024];
int n, m;

void floyd(void)
{
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

void dijkstra(int root)
{
	memset(ds, 0x3f, sizeof(ds));
	memset(ps, 0, sizeof(ps));
	ds[root] = 0;
	while (1) {
		int bi = -1, mdist = inf;
		for (int i = 0; i < n; i++) if (!ps[i] && ds[i] < mdist) {
			mdist = ds[i];
			bi = i;
		}
		if (bi == -1) return;
		ps[bi] = 1;
		for (int i = 0; i < n; i++) 
			if (ds[i] > ds[bi] + g[bi][i]) {
				ds[i] = ds[bi] + g[bi][i];
			}
	}
}



int main(void) 
{
	memset(g, 0x3f, sizeof(g));
	FILE *f = fopen("graph.txt", "rt");
	fscanf(f, "%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		fscanf(f, "%d%d%d", &x, &y, &z);
		g[x][y] = min(g[x][y], z);
	}
	fclose(f);
	printf("Dikstra...");
	dijkstra(0);
	printf("Done\n");
	printf("Floyd...");
	floyd();
	printf("Done\n");
	
	return 0;
}