#include <vector>
#include <cstdio>

using namespace std;

class Vertex;
class Edge
{
    public:
        Edge();
        Edge(Vertex*, Vertex*, int);
        Edge(int, Vertex*, int, Vertex*, int);
        int cost;
        int sourceName, targetName;
        Vertex *source, *target;
    protected:
    private:
};

class Edge;
class Vertex
{
    public:
        Vertex();
        vector<Edge*> in, out;
    protected:
    private:
};

class Graph
{

    public:
        typedef vector<Edge*>::iterator iterator;
        Graph();
        void read(FILE*);
        int getNumberOfVertices();
        int getNumberOfEdges();
        Edge *getEdge(int source, int target);
        int getInDegree(int vertex);
        int getOutDegree(int vertex);
        iterator outboundBegin(int vertex);
        iterator outboundEnd(int Vertex);
        iterator inboundBegin(int vertex);
        iterator inboundEnd(int Vertex);
    protected:
    private:
        int number_of_vertices, number_of_edges;
        vector<Edge*> edges;
        vector<Vertex> vertices;
};

Vertex::Vertex()
{
    //ctor
}

Edge::Edge()
{
    //ctor
}

Edge::Edge(Vertex *source, Vertex *target, int cost) {
    this->source = source;
    this->target = target;
    this->cost = cost;
}

Edge::Edge(int sourceName, Vertex *source, int targetName, Vertex *target, int cost) {
    this->sourceName = sourceName;
    this->targetName = targetName;
    this->source = source;
    this->target = target;
    this->cost = cost;
}

Graph::Graph()
{
    //ctor
}

void Graph::read(FILE *file) {
    int source, target, cost;
    Edge *edge;

    fscanf(file, "%d %d", &number_of_vertices, &number_of_edges);
    vertices.resize(number_of_vertices);
    for (int i=0; i<number_of_edges; ++i) {
        fscanf(file, "%d %d %d", &source, &target, &cost);
        edge = new Edge(source, &vertices[source], target, &vertices[target], cost);
        edges.push_back(edge);
        vertices[source].out.push_back(edge);
        vertices[target].in.push_back(edge);
    }
}

int Graph::getNumberOfVertices() {
    return number_of_vertices;
}

int Graph::getNumberOfEdges() {
    return number_of_edges;
}

Edge* Graph::getEdge(int source, int target) {
    if (source >= number_of_vertices)
        return NULL;
    unsigned int len = vertices[source].out.size();
    for (unsigned int i=0; i<len; ++i) {
        Edge* e = vertices[source].out[i];
        if (e->targetName == target)
            return vertices[source].out[i];
    }
    return NULL;
}

int Graph::getInDegree(int vertex) {
    if (vertex >= number_of_vertices)
        return -1;
    return vertices[vertex].in.size();
}

int Graph::getOutDegree(int vertex) {
    if (vertex >= number_of_vertices)
        return -1;
    return vertices[vertex].out.size();
}

Graph::iterator Graph::outboundBegin(int vertex) {
    /*
     *  the vertex must exists!
     */
    return vertices[vertex].out.begin();
}

Graph::iterator Graph::outboundEnd(int vertex) {
    /*
     *  the vertex must exists!
     */
    return vertices[vertex].out.end();
}

Graph::iterator Graph::inboundBegin(int vertex) {
    /*
     *  the vertex must exists!
     */
    return vertices[vertex].in.begin();
}

Graph::iterator Graph::inboundEnd(int vertex) {
    /*
     *  the vertex must exists!
     */
    return vertices[vertex].in.end();
}




Graph graph;
vector<vector<int> > dist;
int INF = ~(1<<31);

int add(int a, int b) {
	if (a == INF || b == INF)
		return INF;
	return a+b;
}

void printMatrix() {
	for (int i=0; i<graph.getNumberOfVertices(); ++i) {
        for (int j=0; j<graph.getNumberOfVertices(); ++j) 
			printf("%d ", dist[i][j]);
		printf("\n");
	}
}

void floyd(int source, int target) {
	int sum;
    dist.resize(graph.getNumberOfVertices());
    for (int i=0; i<graph.getNumberOfVertices(); ++i)
        dist[i].resize(graph.getNumberOfVertices(), INF);
    
    for (int i=0; i<graph.getNumberOfVertices(); ++i)
        for (int j=0; j<graph.getNumberOfVertices(); ++j) {
			if (i == j) {
				dist[i][j] = 0;
				continue;
			}
			Edge *edge = graph.getEdge(i, j);
			if (edge != NULL)
				dist[i][j] = edge->cost;
		}

    for (int k=0; k<graph.getNumberOfVertices(); ++k)
        for (int i=0; i<graph.getNumberOfVertices(); ++i)
            for (int j=0; j<graph.getNumberOfVertices(); ++j) {
				sum = add(dist[i][k], dist[k][j]);
				if (dist[i][j] > sum)
					dist[i][j] = sum;
            }
	printMatrix();
}

int main () {

    //FILE *file = fopen("graph1m.txt", "r");
    FILE *file = fopen("royfloyd.in", "r");

	freopen("royfloyd.out", "w", stdout);
    graph.read(file);
    printf("V: %d E: %d\n", graph.getNumberOfVertices(), graph.getNumberOfEdges());

    int source, target;
/*    printf("Source: ");
    scanf("%d", &source);
    printf("Target: ");
    scanf("%d", &target);*/
    floyd(source, target);


    return 0;
}