EAGLE1  Eagle and Dogs
Eagle (AKA Mohamed Ahmed) lives in a city consists of n intersections connected by n1 roads, in a way that can go from any intersection to any other intersection moving along some of these roads.
Every day he starts walking in the city following a simple strategy; if he's at some intersection he has to pick one of the roads connected to it at random such that he hasn't walked through it before and walk through it and and if there isn't any, he stops and goes home.
His only problem is that he's afraid of dogs. He doesn't even like seeing dogs. So he's wondering in the worst scenario, how many dogs he'll have to see during his walk until he stops if he starts walking at some intersection. Can you help him?
Input
The input starts with an integer T (1 <= T <= 10), the number of test cases. following T blocks describing each test case.
Each block starts with a line containing an integer n (2 <= n <= 10^{5}), the number of intersections in the city. Intersections are numbers 1 through n.
Followed by n1 lines each containing integers u, v, (1 <= u, v <= n) and d (1 <= d <= 10^{9}), the numbers of intersections at the end of this road and the number od dogs Eagle will see walking in this road.
Output
For each test case print a line containing n integers, the ith integer represents the maximum number of dogs Eagle might see if he starts his walk at intersection i.
Example
Input: 1
4
1 2 3
3 2 4
3 4 5
Output: 12 9 7 12
hide comments
sonukumar:
20210125 21:37:01
try with a single dfs run


lm10_piyush:
20210110 16:44:58
Use DP. 

wille_25:
20201230 16:56:51
tricky problem


ks1999:
20200926 20:15:00
@eagle93: can there be cycles? Last edit: 20200926 21:52:16 

kauai68:
20200509 11:10:01
dfs is not a problem, but how often do you call dfs? 

saifedin6:
20191002 09:16:18
why did I get time limit exceeded ?! I did only use dfs.. 

scorpy1:
20190821 18:34:36
get AC after modifying codes for this such a strict time problem! 

akash13s:
20190124 15:49:47
nice question:) 

gulshan kumar:
20150622 21:03:51
@ivanilos plz provide some hint..I have been using bfs over the graph but geeting time limit exceeded..


ahmed fathy aly:
20150618 18:30:34
a time limit of 1 second is too tight for Java :( Last edit: 20150619 00:28:01 
Added by:  eagle93 
Date:  20150617 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 