/*
TASK:oldmap
LANG:C++
*/

#include <list>
#include <queue>
#include <cstdio>
#include <vector>
#include <climits>

class edge
{
public:
	edge() {}
	edge(const unsigned int& t, const unsigned int& l) : to(t), len(l) {}

	unsigned int to;
	unsigned int len;
};

class path
{
public:
	path() {}
	path(const unsigned int& t, const unsigned int& l, const unsigned int& e) : to(t), len(l), edges(e) {}

	unsigned int to;
	unsigned int len;
	unsigned int edges;
};

class path_more
{
public:
	inline bool operator() (const path& a, const path& b) {return a.len > b.len;}
};

int main()
{
    unsigned int n;
    std::scanf("%u", &n);
    std::vector<std::vector<unsigned int> > g(n);
    for (unsigned int i = 0; i < n; i++)
        g[i].resize(n);
        
    for (unsigned int i = 0; i < n; i++)
        for (unsigned int j = 0; j < n; j++)
			std::scanf("%u", &g[i][j]);
	
	std::vector<std::list<edge> > graph(n);
	for (unsigned int i = 0; i < n; i++)
		for (unsigned int j = 0; j < i; j++)
		{
			graph[i].push_back(edge(j, g[i][j]));
			graph[j].push_back(edge(i, g[i][j]));
		}

	for (unsigned int from = 0; from < n; from++)
	{
		std::priority_queue<path, std::vector<path>, path_more> q;
		q.push(path(from, 0, 0));
		std::vector<unsigned int> pts(n, 0);

		while (!q.empty())
		{
			path p;
			p = q.top(); q.pop();

			if (pts[p.to] < p.edges) pts[p.to] = p.edges;
			
			for (std::list<edge>::iterator it = graph[p.to].begin(); it != graph[p.to].end(); it++)
				if (pts[it->to] < 2 && p.len+it->len <= g[from][it->to])
					q.push(path(it->to, p.len+it->len, p.edges+1));
		}

		for (unsigned int i = 0; i < n; i++)
		{
			//std::printf("%u ", pts[i]);

			if (pts[i] >= 2)
			{
				for (std::list<edge>::iterator it = graph[from].begin(); it != graph[from].end(); it++)
					if (it->to == i)
					{
						graph[from].erase(it);
						break;
					}

				for (std::list<edge>::iterator it = graph[i].begin(); it != graph[i].end(); it++)
					if (it->to == from)
					{
						graph[i].erase(it);
						break;
					}
			}
		}

		//std::printf("\n");
	}

	for (unsigned int i = 0; i < n; i++)
		for (std::list<edge>::iterator it = graph[i].begin(); it != graph[i].end(); it++)
			if (i < it->to)
				std::printf("%u %u %u\n", i+1, it->to+1, it->len);
    
    return 0;
}
