p206.ans1
======================
4
5
4
5
4

=================
p206.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/hungarian_algorithm.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T>
class HungarianAlgorithm {
  private:
    const T INF = numeric_limits<T>::max() / 2;
    vector<int> way;

  public:
    int n, m;
    vector<vector<T>> cost;
    vector<int> assignment;
    vector<T> pot_left, pot_right;

    HungarianAlgorithm(const vector<vector<T>>& a) {
        n = a.size();
        m = a[0].size();
        assert(n <= m);

        cost.assign(n + 1, vector<T>(m + 1));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cost[i][j] = a[i][j];
            }
        }

        pot_left.assign(n + 1, 0);
        pot_right.assign(m + 1, 0);
        assignment.assign(m + 1, n);
        way.assign(m + 1, m);

        for(int i = 0; i < n; i++) {
            assignment[m] = i;
            int j0 = m;
            vector<T> minv(m + 1, INF);
            vector<bool> used(m + 1, false);
            do {
                used[j0] = true;
                int i0 = assignment[j0], j1 = m;
                T delta = INF;
                for(int j = 0; j < m; j++) {
                    if(!used[j]) {
                        T cur = cost[i0][j] - pot_left[i0] - pot_right[j];
                        if(cur < minv[j]) {
                            minv[j] = cur;
                            way[j] = j0;
                        }
                        if(minv[j] < delta) {
                            delta = minv[j];
                            j1 = j;
                        }
                    }
                }
                for(int j = 0; j <= m; j++) {
                    if(used[j]) {
                        pot_left[assignment[j]] += delta;
                        pot_right[j] -= delta;
                    } else {
                        minv[j] -= delta;
                    }
                }
                j0 = j1;
            } while(assignment[j0] != n);

            do {
                int j1 = way[j0];
                assignment[j0] = assignment[j1];
                j0 = j1;
            } while(j0 != m);
        }
    }

    T get_cost() {
        T ans = 0;
        for(int j = 0; j < m; j++) {
            ans += cost[assignment[j]][j];
        }
        return ans;
    }
};

int n, m;
vector<vector<pair<int, int>>> tree_adj;
vector<tuple<int, int, int>> edges;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(auto& [u, v, w]: edges) {
        cin >> u >> v >> w;
        u--, v--;
    }
}

bool add_on_path(
    int u, int par, int tgt, int edge_tgt, vector<vector<int64_t>>& matrix
) {
    if(u == tgt) {
        return true;
    }

    for(auto [v, idx]: tree_adj[u]) {
        if(v != par && add_on_path(v, u, tgt, edge_tgt, matrix)) {
            matrix[idx][edge_tgt] = min<int64_t>(
                matrix[idx][edge_tgt],
                get<2>(edges[edge_tgt]) - get<2>(edges[idx])
            );
            return true;
        }
    }

    return false;
}

void solve() {
    // This is the inverse minimum spanning tree problem: we want to change the
    // weights as little as possible (in L1 distance) so that the first n-1
    // edges (the given tree) become a minimum spanning tree. By the MST
    // optimality condition, the tree is minimal iff for every non-tree edge e
    // its weight is at least the weight of every tree edge on the cycle it
    // closes. We may only raise tree-edge weights (potentials pot_left) and
    // lower non-tree-edge weights (potentials pot_right). For each non-tree
    // edge i and each tree edge idx on its tree path we build a cost matrix
    // matrix[idx][i] = new_w(i) - new_w(idx) lower bound, and minimizing total
    // L1 change subject to all these constraints is exactly an assignment
    // (Hungarian) problem on this matrix. The optimal potentials give the
    // reported costs: tree edges get raised by pot_left, non-tree edges get
    // lowered by pot_right.

    vector<vector<int64_t>> matrix(n - 1, vector<int64_t>(m, 0));

    tree_adj.assign(n, {});
    for(int i = 0; i < n - 1; i++) {
        auto [u, v, _] = edges[i];
        tree_adj[u].push_back({v, i});
        tree_adj[v].push_back({u, i});
    }

    for(int i = n - 1; i < m; i++) {
        auto [u, v, w] = edges[i];
        add_on_path(u, u, v, i, matrix);
    }

    auto hungarian = HungarianAlgorithm<int64_t>(matrix);
    for(int i = 0; i < n - 1; i++) {
        cout << get<2>(edges[i]) + hungarian.pot_left[i] << '\n';
    }
    for(int i = n - 1; i < m; i++) {
        cout << get<2>(edges[i]) - hungarian.pot_right[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p206.in1
======================
4 5
4 1 7
2 1 5
3 4 4
4 2 5
1 3 1

=================
statement.txt
======================
206. Roads
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The kingdom of Farland has N cities connected by M roads. Some roads are paved with stones, others are just country roads. Since paving the road is quite expensive, the roads to be paved were chosen in such a way that for any two cities there is exactly one way to get from one city to another passing only the stoned roads.

The kingdom has a very strong bureaucracy so each road has its own ordinal number ranging from 1 to M: the stoned roads have numbers from 1 to N-1 and other roads have numbers from N to M. Each road requires some money for support, i-th road requires ci coins per year to keep it intact. Recently the king has decided to save some money and keep financing only some roads. Since he wants his people to be able to get from any city to any other, he decided to keep supporting some roads in such a way, that there is still a path between any two cities.

It might seem to you that keeping the stoned roads would be the good idea, however the king did not think so. Since he did not like to travel, he did not know the difference between traveling by a stoned road and travelling by a muddy road. Thus he ordered you to bring him the costs of maintaining the roads so that he could order his wizard to choose the roads to keep in such a way that the total cost of maintaining them would be minimal.

Being the minister of communications of Farland, you want to help your people to keep the stoned roads. To do this you want to fake the costs of maintaining the roads in your report to the king. That is, you want to provide for each road the fake cost of its maintaining di in such a way, that stoned roads form the set of roads the king would keep. However, to lower the chance of being caught, you want the value of sum(i = 1..M, |ci-di|) to be as small as possible.

You know that the king's wizard is not a complete fool, so if there is the way to choose the minimal set of roads to be the set of the stoned roads, he would do it, so ties are allowed.

Input
The first line of the input file contains N and M (2 ≤ N ≤ 60, N-1 ≤ M ≤ 400). Next M lines contain three integer numbers ai, bi and ci each — the numbers of the cities the road connects (1 ≤ ai ≤ N, 1 ≤ bi ≤ N, ai ≠ bi) and the cost of maintaining it (1 ≤ ci ≤ 10 000).

Output
Output M lines — for each road output di that should be reported to be its maintainance cost so that he king would choose first N-1 roads to be the roads to keep and the specified sum is minimal possible.

Sample test(s)

Input
4 5
4 1 7
2 1 5
3 4 4
4 2 5
1 3 1

Output
4
5
4
5
4
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-23








=================
