Shortest Delivery Time

You are given n houses labeled from 1 to n and m bidirectional roads connecting these houses. Each road connects two houses and has a travel time t on a sunny day. When the weather is rainy, the travel time on every road becomes doubled, that is, if the usual travel time is t, then in rainy weather it becomes $$2 \times t$$.

Your task is to compute the shortest delivery times from the post office at house 1 to every other house. If a house is unreachable, output -1 for that house.

inputFormat

The input is read from stdin and has the following format:

 n m
 u1 v1 t1
 u2 v2 t2
 ...
 um vm tm
 weather

Where:

• n is the number of houses.
• m is the number of roads.
• Each of the next m lines contains three integers u, v, and t indicating that there is a road between house u and house v with travel time t on a sunny day.
• weather is a string that is either "sunny" or "rainy".

outputFormat

Output a single line to stdout containing n-1 space‐separated integers. The i-th integer represents the shortest delivery time from house 1 to house i+1. If a house is unreachable, output -1 for that house.

4 4
1 2 5
1 3 10
2 4 5
3 4 5
sunny

5 10 10