<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
1. Abridged Problem Statement  
We are given an undirected graph with N vertices and M edges. Edges 1 through N–1 form a spanning tree T (the “stoned” roads). Each edge i has a true maintenance cost cᵢ. We want to report fake costs dᵢ so that, if someone runs a minimum‐spanning‐tree algorithm on the graph with weights dᵢ, the unique (or tied‐for‐minimum) MST is exactly T. Among all such choices of d, we must minimize  
   ∑_{i=1..M} |cᵢ – dᵢ|.  

2. Key Observations  
- To force T to be an MST, every non‐tree edge j must not be strictly cheaper (under the fake costs) than every tree edge i on the unique path in T between j’s endpoints.  
- Equivalently, if we define  
     xᵢ ≥ 0  as the amount we increase the cost of tree edge i,  
     yⱼ ≥ 0  as the amount we decrease the cost of non‐tree edge j,  
  then the fake costs are  
     dᵢ = cᵢ + xᵢ   for i in T,  
     dⱼ = cⱼ – yⱼ   for j ∉ T,  
  and we require for every non‐tree edge j and every tree‐edge i on its tree‐path:  
     (cᵢ + xᵢ)  ≤  (cⱼ – yⱼ),  
  i.e.  
     xᵢ + yⱼ  ≤  cⱼ – cᵢ.  
- Our goal is to minimize ∑ xᵢ + ∑ yⱼ subject to those linear constraints.  This is a special linear program whose dual is a maximum‐weight “potential” problem on a bipartite graph between the N–1 tree edges and the M total edges.  By strong duality and total unimodularity, the integer optimum equals the real optimum.  
- The dual formulation can be solved by the Hungarian (Kuhn–Munkres) algorithm on a cost matrix A of size (N–1)×M, where  
     A[i][j] = cⱼ – cᵢ   if tree‐edge i lies on the path in T between the endpoints of edge j,  
     A[i][j] = ∞ otherwise.  
  The Hungarian algorithm finds dual potentials u[i] (for rows i=1..N–1) and v[j] (for cols j=1..M) maximizing ∑ u[i] + ∑ v[j] under u[i] + v[j] ≤ A[i][j].  Those potentials turn out to equal xᵢ = u[i] and yⱼ = v[j].  

3. Full Solution Approach  
1. Read N, M and the list of edges (uᵢ, vᵢ, cᵢ).  The first N–1 edges form the tree T.  
2. Build an adjacency list for T using edges 1..N–1.  
3. Initialize an (N–1)×M matrix A with a very large value (∞).  
4. For each non‐tree edge j = N..M:  
   a. Let its endpoints be (u, v).  
   b. Run a DFS from u to v in the tree T, tracking the tree‐edges on that path.  
   c. For each tree‐edge i on the path, set  
        A[i][j] = min( A[i][j],  cⱼ – cᵢ ).  
5. Run the Hungarian algorithm on matrix A (size (N–1)×M).  It returns dual arrays u[1..N–1], v[1..M].  
6. Set  
      For i=1..N–1:   dᵢ = cᵢ + u[i]  
      For j=N..M:     dⱼ = cⱼ – v[j]  
7. Output d₁ through d₍M₎.  

This guarantees that T is an MST under weights d, and ∑|cᵢ – dᵢ| = ∑ xᵢ + ∑ yⱼ is minimized.  

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e15;

// Hungarian algorithm for a rectangular cost matrix of size n×m, n ≤ m.
// Given cost[1..n][1..m], it finds a matching of size n minimizing total cost.
// It also produces dual potentials u[1..n], v[1..m] so that
//   u[i] + v[j] ≤ cost[i][j]  for all i,j
// and ∑u[i] + ∑v[j] is maximized.
struct Hungarian {
    int n, m;
    vector<vector<ll>> cost;
    vector<ll> u, v;
    vector<int> p, way;

    // costMatrix is 0-based of size n×m
    Hungarian(const vector<vector<ll>>& costMatrix) {
        n = costMatrix.size();
        m = costMatrix[0].size();
        // Internally use 1-based arrays of size (n+1)×(m+1)
        cost.assign(n+1, vector<ll>(m+1, 0));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cost[i][j] = costMatrix[i-1][j-1];

        u.assign(n+1, 0);
        v.assign(m+1, 0);
        p.assign(m+1, 0);
        way.assign(m+1, 0);

        // For each row i, we add it to the matching
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            ll j0 = 0;
            vector<ll> minv(m+1, INF);
            vector<char> used(m+1, false);

            // Find augmenting path
            do {
                used[j0] = true;
                int i0 = p[j0];
                ll delta = INF, j1 = 0;

                for (int j = 1; j <= m; j++) {
                    if (used[j]) continue;
                    ll cur = cost[i0][j] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }

                // Update potentials
                for (int j = 0; j <= m; j++) {
                    if (used[j]) {
                        u[p[j]] += delta;
                        v[j] -= delta;
                    } else {
                        minv[j] -= delta;
                    }
                }
                j0 = j1;
            } while (p[j0] != 0);

            // Augment the matching
            do {
                int j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0 != 0);
        }
        // Now u[1..n], v[1..m] are the dual potentials.
    }
};

int N, M;
vector<tuple<int,int,int>> edges;
vector<vector<pair<int,int>>> treeAdj;  
// treeAdj[u] = list of (v, edgeIndex) for tree edges

// DFS to mark all tree-edges on the path from u to target.
// Whenever we go through a tree-edge idx on that path, we update
// matrix[idx][edgeJ] = min(matrix[idx][edgeJ], cJ - c_idx)
bool dfs_path(int u, int parent, int target, int edgeJ,
              vector<vector<ll>>& matrix) {
    if (u == target) return true;
    for (auto &pr: treeAdj[u]) {
        int v = pr.first, idx = pr.second;
        if (v == parent) continue;
        if (dfs_path(v, u, target, edgeJ, matrix)) {
            // edge idx is on the path
            int cJ = get<2>(edges[edgeJ]);
            int cI = get<2>(edges[idx]);
            matrix[idx][edgeJ] = min(matrix[idx][edgeJ], (ll)(cJ - cI));
            return true;
        }
    }
    return false;
}

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

    cin >> N >> M;
    edges.resize(M);
    for (int i = 0; i < M; i++) {
        int u,v,c; 
        cin >> u >> v >> c;
        --u; --v;
        edges[i] = make_tuple(u, v, c);
    }

    // Build tree adjacency for edges 0..N-2
    treeAdj.assign(N, {});
    for (int i = 0; i < N-1; i++) {
        int u,v,c;
        tie(u,v,c) = edges[i];
        treeAdj[u].push_back({v,i});
        treeAdj[v].push_back({u,i});
    }

    // Prepare the cost matrix A of size (N-1)×M, initialize to INF
    vector<vector<ll>> A(N-1, vector<ll>(M, INF));

    // For each non-tree edge j = N-1..M-1, find its path in T
    for (int j = N-1; j < M; j++) {
        int u,v,c; 
        tie(u,v,c) = edges[j];
        dfs_path(u, -1, v, j, A);
    }

    // Run Hungarian on A
    Hungarian hung(A);

    // Recover fake costs
    // For tree edges i=0..N-2, d = c + u[i+1]
    for (int i = 0; i < N-1; i++) {
        int c = get<2>(edges[i]);
        ll di = c + hung.u[i+1];
        cout << di << "\n";
    }
    // For non-tree edges j=N-1..M-1, d = c - v[j+1]
    for (int j = N-1; j < M; j++) {
        int c = get<2>(edges[j]);
        ll dj = c - hung.v[j+1];
        cout << dj << "\n";
    }
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
sys.setrecursionlimit(10000)
INF = 10**15

def hungarian(cost):
    # cost is an n×m list of lists, with n ≤ m
    n, m = len(cost), len(cost[0])
    # 1-based arrays
    u = [0] * (n+1)
    v = [0] * (m+1)
    p = [0] * (m+1)
    way = [0] * (m+1)

    for i in range(1, n+1):
        p[0] = i
        minv = [INF] * (m+1)
        used = [False] * (m+1)
        j0 = 0
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = INF
            j1 = 0
            # Try to extend matching to a new column
            for j in range(1, m+1):
                if used[j]:
                    continue
                cur = cost[i0-1][j-1] - u[i0] - v[j]
                if cur < minv[j]:
                    minv[j] = cur
                    way[j] = j0
                if minv[j] < delta:
                    delta = minv[j]
                    j1 = j
            # Update duals
            for j in range(m+1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        # Augment the matching
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break

    # u[1..n], v[1..m] are the dual potentials
    return u, v

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    edges = []
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        c = int(next(it))
        edges.append((u,v,c))

    # Build tree adjacency for first N-1 edges
    tree_adj = [[] for _ in range(N)]
    for i in range(N-1):
        u,v,c = edges[i]
        tree_adj[u].append((v,i))
        tree_adj[v].append((u,i))

    # Prepare the cost matrix A of size (N-1)×M
    A = [[INF]*M for _ in range(N-1)]

    # DFS to find the path from u to target in T
    def dfs(u, parent, target, j_edge):
        if u == target:
            return True
        for v, idx in tree_adj[u]:
            if v == parent:
                continue
            if dfs(v, u, target, j_edge):
                cJ = edges[j_edge][2]
                cI = edges[idx][2]
                A[idx][j_edge] = min(A[idx][j_edge], cJ - cI)
                return True
        return False

    # Fill A for each non-tree edge
    for j in range(N-1, M):
        u,v,c = edges[j]
        dfs(u, -1, v, j)

    # Run Hungarian to get dual potentials
    u_pot, v_pot = hungarian(A)

    # Output the fake costs
    out = []
    # Tree edges i=0..N-2: increase by u_pot[i+1]
    for i in range(N-1):
        c = edges[i][2]
        out.append(str(c + u_pot[i+1]))
    # Non-tree edges j=N-1..M-1: decrease by v_pot[j+1]
    for j in range(N-1, M):
        c = edges[j][2]
        out.append(str(c - v_pot[j+1]))

    print("\n".join(out))

if __name__ == "__main__":
    main()
```