Some random graph problem

0

0 votes
Problem

There are N countries numbered from 1 to N, with M bidirectional roads connecting them, each road has some given length, the ith road connects countries ui and vi and takes time wi to pass. However, due to the last war that happened a few centuries ago, some countires have formed Ally groups. There are a total of K ally groups (Note that countires can be part of more than 1 ally groups). The ith of these groups has size szi you are allowed to teleport from any country in the ith ally group to any other country in the ith ally group in some fixed time - timei. One day you became curious how long it would take to reach all of the countries from 1, however there are too many countries and roads so you decided to write a program to solve your problem.

 

Constraints -

1 <= N,K <= 105

1 <= M <= 2*105

1 <= ui, vi <= N,  (ui != vi)

1 <= wi, timei <= 109

1 <= sz<= 10(It is guaranteed that the sum of sizes of all groups doesn't exceed 100000)

Input format -

The first line contains three integers N, M and K.

The next M lines contain 3 integers each, u,v and w, denoting that there is a road from country u to v which takes a time of w to pass

The next 2*K lines provide a description of the ally groups, each group is described in two lines as follows

The first line contains two integers sizei and timei, denoting the size of the group and the amount of time it takes to teleport

The second line contains sizei integers, denoting the members of the group

 

Output format -

Output N-1 integers in a single line, the minimum amount of time it takes to reach countires 2,3,4... N starting from 1. (It is guaranteed that the graph is connected)

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

2, 3 and 4 can be reached fastest by roads, but 5 can be reached fastest by teleporting from 1 to 5 (ally group 1)

Editor Image

?