Description

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi  ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

Input

* Line 1: Four space-separated integers: N, T, S, and E

* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

Output

* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

Sample Input

2 6 6 4

11 4 6

4 4 8

8 4 9

6 6 8

2 6 9

3 8 9

Sample Output

10

Source

USACO 2007 November Gold

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<string>

 #include<map>

 #define ll long long

 using namespace std;

 ll n,m,S,T,l;

 map<ll,ll>id;

 struct node{

     ll a[][];

     friend node operator *(node x,node y)

     {

          node z;

          memset(z.a,0x3f,sizeof(z.a));

          for(ll k=;k<=l;k++)

           for(ll i=;i<=l;++i)

            for(ll j=;j<=l;++j)

             z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]);

          return z;

     }

 }s,ans;

 void ksm()

 {

     ans=s;

     n--;

     while(n)

     {

         if(n&) ans=ans*s;

         s=s*s;

         n>>=;

     }

 }

 int main()

 {

     freopen("run.in","r",stdin);

     freopen("run.out","w",stdout);

     memset(s.a,0x3f,sizeof(s.a));

     scanf("%lld%lld%lld%lld",&n,&m,&S,&T);

     for(ll i=,x,y,z;i<=m;++i)

     {

        scanf("%lld%lld%lld",&z,&x,&y);

        if(id[x]) x=id[x];

        else l++,id[x]=l,x=l;

        if(id[y]) y=id[y];

        else l++,id[y]=l,y=l;

        s.a[x][y]=s.a[y][x]=z;

     }

     S=id[S];T=id[T];

     ksm();

     printf("%lld",ans.a[S][T]);

     return ;

 }

 /*

 2 6 6 4

 11 4 6

 4 4 8

 8 4 9

 6 6 8

 2 6 9

 3 8 9

 10

 */