P3008 [USACO11JAN] Roads and Planes G

Farmer John is conducting research for a new milk contract in a new territory. He intends to distribute milk to T (1

\* Line 1: Four space separated integers: T, R, P, and S \* Lines 2..R+1: Three space separated integers describing a road: A\_i, B\_i and C\_i \* Lines R+2..R+P+1: Three space separated integers describing a plane: A\_i, B\_i and C\_i

\* Lines 1..T: The minimum cost to get from town S to town i, or 'NO PATH' if this is not possible

6 towns. There are roads between town 1 and town 2, town 3 and town 4, and town 5 and town 6 with costs 5, 5 and 10; there are planes from town 3 to town 5, from town 4 to town 6, and from town 1 to town 3 with costs -100, - 100 and -10. FJ is based in town 4. FJ's cows begin at town 4, and can get to town 3 on the road. They can get to towns 5 and 6 using planes from towns 3 and 4. However, there is no way to get to towns 1 and 2, since they cannot go backwards on the plane from 1 to 3.