#include <iostream>
using namespace std;
int main() {
    int n, a[100][100], b[100][100], c[100][100], max = 0, v1 = 0, v2 = 0;
    // Nhap mang 2 chieu mo ta do thi, -1 la ko co duong noi truc tiep, 0 la i==j, >0 khi co duong
    // noi truc tiep giua i va j do anh!
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            a[i][j] = -1;
    for (int i = 0; i < 100; i++)
        a[i][i] = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int u, v, k;
            cin >> u >> v >> k;
            a[i][j] = k;
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i][j] = b[i][j] = a[i][j];

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j) {
                    if (b[i][k] + b[k][j] > b[i][j]) {
                        c[i][j] = b[i][k] + b[k][j];
                    } else
                        c[i][j] = b[i][j];

                } else
                    c[i][j] = b[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                b[i][j] = c[i][j];
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (c[i][j] > max) {
                max = c[i][j];
                v1  = i;
                v2  = j;
            }

    printf("Quang duong dai nhat noi 2 diem %d va %d la %d\n", v1, v2, max);
}