X, the sweet_distributer lives in locality 1. This time he has been assigned the task to deliver the diwali sweets to each of the locality except his own. So, he has to deliver sweets to all the localities.He can deliver the sweet box in any order. But,the issue is he can carry only 1 sweet box at a time.So, he has to return to his own locality after delivery of each box, if there is any other locality left. Travelling from one locality to another takes time. So, X wants your help in minimizing the time to distribute the sweet boxes.The localities are connected by one-way streets.
Print the sum of minimum time taken to complete the task, and print -1 if X cannot deliver sweets to all the localities.
Constraints:
the graph is Connected and directed and may contain multiple edges and self loops.
1<=n<=1000
n<=m<=n*(n+1)
1<=travelling time from one locality to another<=100
Input Format:
n - number of localities
m - number of streets connecting the localities
Next m line contains 3 integers-
x,y,z - locality x is connected with locality y and z is the time to travel from x to y
Output format:
Print the minimum time if possible,else -1.
First, he visits 4, time = 6 then he returns to 1,time = 5 then he visits 3, time = 3 then he returns to 1,time = 8 then he visits 2, time = 2 all the sweets are delivered, so he doesn't return. total time = 6+5+3+8+2 = 24