Farmer John正在一个新的销售区域对它的牛奶销售方案进行调查。他想把牛奶送到T个城镇（1≤T≤25000），编号为1~T。这些城镇之间通过R条道路（1≤R≤50000，编号为1到R）和P条航线（1≤P≤50000，编号为1到P）连接。每条道路i或者航线i连接城镇Ai（1≤Ai≤T）到Bi（1≤Bi≤T），花费为Ci。对于道路，0≤Ci≤10000，然而航线的花费很神奇，花费Ci可能是负数（-10000≤Ci≤10000）。道路是双向的，可以从Ai到Bi，也可以从Bi到Ai，花费都是Ci。然而航线与之不同，只可以从Ai到Bi。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，政府出台了一些政策保证：如果一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai。由于Farmer John的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到发送中心镇S（1≤S≤T）把奶牛送到每个城镇的最便宜的方案或者知道这是不可能的。