SPHIWAY - Two "Ways"

There are N places and M bidirectional way. No two places have more than one direct way. Ana wants to walk from S to T and return to S by a itinerary that satisfy:

  • No way can be go twice.
  • Length of itinerary is the minimum.

Input

Line 1: 4 integers: N, M, S, T (N <= 104; M <= 105)

Next M line: Line i include 3 integers ui, vi, ci: distance of two places ui and vi is ci. (ci <= 2000000000).

Output

Length of the itinerary if it exists. Else print -1.

Example

Input:
5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3

Output:
24

Added by:HNUE
Date:2009-10-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Mr. Le Minh Hoang - HNUE

hide comments
2010-03-10 01:31:35 Tony Beta Lambda
LLONG_MAX (C99 Page 22, 5.2.4.2.1) does not exist. Why?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.