github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: KOL1507
problem_name: 'The Christmas Cookies'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '1.5'
source_sizelimit: '50000'
problem_author: devuy11
problem_tester: null
date_added: 10-12-2015
tags:
    - acm15kol
    - decomposition
    - devuy11
    - heavy
    - range
    - spanningtree
editorial_url: 'http://discuss.codechef.com/problems/KOL1507'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493557724
layout: problem
---
All submissions for this problem are available.CodeChef has prepared christmas cookies for everyone in the town. He gives the responsibility of distributing the cookies to Samosa Bhai.

There are **N** houses and **E** roads in the town. Each road starts from one house and ends at another and there are no other houses on the road. **There can be more than one direct road between two houses**. Each road has some road tax. Once you have paid the road tax for a road, you can travel on that road any number of times. The problem is, a Christmas tree has to be installed in the town. It can only be installed on one of the roads resulting in that road being blocked. As a result, Samosa Bhai will not be able to use that road for travelling.

Now, **for each road**, Samosa Bhai wants to know the minimum amount of road tax he will have to pay to distribute candies in all the houses, if the Christmas tree were to be placed on that road. Samosa Bhai can start his journey from any of the houses.

### Input

The first line contains **T**, the number of test cases to follow.

The first line of each test case contains the integers **N** and **E** separated by a space.

Next, **E** lines follow. Each line contains three space-separated integers — **x**, **y**, and the road tax of a direct road between house **x** and house **y**.

### Output

For each road (in the **same order as input**), output the value of the minimum road tax paid if the christmas tree is placed on that road and it is still possible to distribute cookies in all houses, otherwise output **-1**.

### Constraints

- **1** ≤ **T** ≤ **1000**
- **1** ≤ **N** ≤ **105**
- **1** ≤ **E** ≤ **2\*105**
- **1** ≤ **Sum of E over all cases** ≤ **2\*105**
- **1** ≤ **Sum of N over all cases** ≤ **105**
- **1** ≤ **Road Tax** ≤ **108**

### Example

<pre><b>Input:</b>
1
5 7
1 2 2
1 4 4
2 3 6
2 5 8
3 5 10
4 3 12
1 5 14

<b>Output:</b>
30
28
24
22
20
20
20
</pre>### Explanation

**Example case 1**

- Road from House 1 to House 2 (i.e Road 1) is blocked: 
  
  Use Roads 2, 3, 4 and 6. Total Tax paid = 30
- Road from House 1 to House 4 (i.e Road 2) is blocked: 
  
  Use Roads 1, 3, 4 and 6. Total Tax paid = 28
- Road from House 2 to House 3 (i.e Road 3) is blocked: 
  
  Use Roads 1, 2, 4 and 5. Total Tax paid = 24