解法

$O(N)$。 $2$進数でやると$N \le 20$なので足りないが、$3$進数でやると上手く収まる。 辺重み$w \le 10^6$という制約に注意。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;

constexpr int N = 20;
constexpr int MAX_L = 1000000;
constexpr int K = 13;
vector<tuple<int, int, int> > solve(int l) {
    vector<int> e(K + 1);
    e[0] = 1;
    REP (k, K) e[k + 1] = 3 * e[k];
    assert (e[K - 1] < MAX_L and MAX_L < e[K]);

    assert (l <= MAX_L);
    vector<int> trits;
    for (int acc = l; acc; acc /= 3) {
        trits.push_back(acc % 3);
    }

    vector<tuple<int, int, int> > edges;
    REP (k, (int)trits.size() - 1) {
        edges.emplace_back(N - k - 2, N - k - 1, 0);
        edges.emplace_back(N - k - 2, N - k - 1, e[k]);
        edges.emplace_back(N - k - 2, N - k - 1, 2 * e[k]);
    }
    int acc = 0;
    REP_R (k, trits.size()) {
        if (trits[k] == 1) {
            edges.emplace_back(0, N - k - 1, acc);
        } else if (trits[k] == 2) {
            edges.emplace_back(0, N - k - 1, acc);
            edges.emplace_back(0, N - k - 1, acc + e[k]);
        }
        acc += trits[k] * e[k];
    }

    array<bitset<MAX_L>, N> dp = {};
    dp[0][0] = true;
    REP (i, N - 1) {
        for (auto edge : edges) {
            int u, v, w; tie(u, v, w) = edge;
            if (u != i) continue;
            assert (dp[u].count() == (dp[u] << w).count());
            assert ((dp[v] & (dp[u] << w)).none());
            dp[v] |= dp[u] << w;
        }
    }
    assert (dp[N - 1].count() == l and (dp[N - 1] >> l).none());
    assert (edges.size() <= 60);
    return edges;
}

int main() {
    int l; cin >> l;
    auto edges = solve(l);
    cout << N << ' ' << edges.size() << endl;
    for (auto edge : edges) {
        int u, v, w; tie(u, v, w) = edge;
        cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
    }
    return 0;
}