Relay Race is a great team game that has attracted generations of Bytelandian children.

Team members are numbered from 0 upto N-1 for a team of N persons. In the game there is a baton(a short stick) which is initially in the hands of the captain (0 numbered person) and the baton needs to be transferred to the K numbered person by passing through all the team members. The game will end when the baton will be in the hands of the K numbered person.

-> Each of the team member can run and pass the baton to every other team member and all the team members are initially standing at a given fixed distance from the other members.

->Every team wants to minimize the total distance traversed by its members by the end of game.

-> The baton must pass through each team member exactly once.

Find the minimum distance required for transferring the baton from the captain to the K numbered person by passing through each team member exactly once.

Input

First line contains two space separated integers N and K denoting the number of team members and the number of the person which will end the game. The next (N*(N-1))/2 lines contain 3 space separated integers A B D denoting that the distance between the members numbered A and B is D units.

Output

Output an integer denoting the least distance required to complete the race.

Constraints

2 <= N <= 20

0 <= A,B <= 19

1 <= D <= 10^6.

program

Sample Input (Plaintext Link)

5 4

0 1 4

0 2 3

0 3 6

0 4 10

1 2 4

1 3 5

1 4 5

2 3 3

2 4 7

3 4 8

expected output:

16

Path giving the minimum distance is 0 -> 2 -> 3 -> 1 -> 4

And minimum distance is given by dist(0,2) + dist(2,3) + dist(3,1) + dist(1,4) i.e. 3 + 3 + 5 + 5 = 16

```
#include<iostream>
```

using namespace std;

int d[20];

int counts=0;

long int ans[20];

long int findd(long int a[][20],int r,int nc) //function to find the min element in r row

{ int check(int); //function to check if the given index is already visited

int k;

long int mind=0; //to store the min no.

for(k=0;k<nc;++k)

{ if(mind>a[r][k]&&check(k))

mind=a[r][k];

}

return mind;

++counts;

d[counts]=k;

}

int check(int j) // to check if index j is already visited

{ int i;

if(counts==0)

{d[0]=0;

return 1;}

else

for(i=0;i<counts;++i)

{

if(d[i]==j)

return 0;

}

}

int main()

{ void cal(int f,int n,long int dist[][20]);

int fcount=counts;

int n,f;

cin>>n>>f;

long int findd(long int a[][20],int r,int nc);

long int dist[n][n];

int t=(n*(n-1))/2;

while(t)

{

int i,j;

cin>>i;

cin>>j;

cin>>dist[i][j];

dist[i][j]=dist[j][i];

–t;

}

cal(f,n,dist);

long int sum=0;

for(int g=0;g<counts;++g)

{

sum=sum+ans[g];

}

cout<<sum;

}

void cal(int f,int n,long int dist[][20])

{ int fcount=0;

int p=0;

while(p!=f)

{

ans[fcount]=findd(dist,p,n);

++fcount;

}

ans[fcount]=findd(dist,f,n);

}