You are given a 2D array $d$ of size $n \times n$. You build a weighted directed graph with $n$ vertices such that $\sum_{i, j} |d[i][j] - dis(i, j)|$ becomes minimum. Here, $dis(i, j)$ represents the shortest distance from vertex $i$ to vertex $j$. If there is no path starting from $i$ and ending at $j$, you will receive a Wrong Answer verdict.

Input format

• The first line contains $n$.
• The next $n$ lines contain array $d$.

Output format

In the first line, print $m$ denoting the number of edges. $0 \le m \le n \times (n - 1)$

In the next $m$ lines, print edges in form $v\ u\ w$. $1 \le v, u \le n, 0 \le w \le 10^5$

Constraints

$n = 100$

$0 \le d_{i, j} \le 10^5$

Checker code

// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!

#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 1e3 + 14;

int n, d[MAX_N][MAX_N];
vector<pair<int, int> > g[MAX_N];
set<pair<int, int> > pq;
int dis[MAX_N];
void dij(int source){
    fill(dis, dis + n, 1e9);
    dis[source] = 0;
    pq.insert({0, source});
    while(pq.size()){
        int v = pq.begin() -> second;
        pq.erase(pq.begin());
        for(auto e : g[v])
            if(dis[e.first] > dis[v] + e.second){
                pq.erase({dis[e.first], e.first});
                pq.insert({dis[e.first] = dis[v] + e.second, e.first});
            }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> d[i][j];
        }
    }
    size_t m;
    cin >> m;
    assert(m <= n * (n - 1));
    for (int i = 0; i < m; ++i) {
        size_t v, u, w;
        cin >> v >> u >> w;
        --v;
        --u;
        assert(v < n && u < n && w <= 1e5);
        g[v].emplace_back(u, w);
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        dij(i);
        for (int j = 0; j < n; ++j) {
            assert(dis[j] < 1e9);
            ans += abs(d[i][j] - dis[j]);
        }
    }
    cout << ans + 1 << '\n';
}

Naive solution

// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!

#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 1e5 + 14;

int n;

int main() {
    cin >> n;
    cout << n << '\n';
    for (int i = 0; i < n; ++i) {
        cout << i + 1 << ' ' << (i + 1) % n + 1 << ' ' << 1 << '\n';
    }
}