#include "stdafx.h"

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int a[101][101],c[101],v1,v2,n,m;

void p(int k, int v)

{c[k]=v;

if (v==v2 || k>=n) {

if (v==v2)

{

//for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl;

int s=0;

for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]];

//cout<<"s="<<s<<endl;

if (s<m) m=s;

}

}

else

for (int i=1;i<=n;i++)

if (a[v][i]>0) p(k+1,i);

}

int main()

{int i,j,t,k;

cin>>n>>m;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)a[i][j]=0;

for (k=1;k<=m;k++)

{cin>>i>>j>>t;

a[i][j]=t;a[j][i]=t;

}

cin>>v1>>v2;

/* for (i=1;i<=n;i++){

for (j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

*/

//cout<<v1<<" "<<v2<<endl;

m=10000000;

p(1,v1);

if (m>=10000000)m=-1;

cout<<m<<endl;

return 0;

}

program Project2;

{$APPTYPE CONSOLE}

var a:array[1..100,1..100] of integer;

smin,i,j,k,l,n,s:integer;

rez,c:array [1..100]of integer;

f1,f2:text;

function f(nn,vv:integer):boolean;

var pr:boolean;

i:integer;

begin

pr:=true;

for i:=1 to nn do

if vv=c[i] then pr:=false;

f:=pr;

end;

procedure p(ni,v:integer);

var s,ii:integer;

begin

c[ni]:=v;

if(ni=n)then begin

{***** 1}

s:=0;

for ii:=1 to ni-1 do s:=s+a[c[ii],c[ii+1]];

s:=s+a[c[n],c[1]];

if s<smin then begin

for ii:=1 to ni do rez[ii]:=c[ii];

smin:=s;

end;

end

else

for ii:=1 to n do

if (a[v,ii]>0)and (f(ni,ii)) then p(ni+1,ii);

end;

begin

assign(f1,'graph.dat');reset(f1);assign(f2,'graph.sol');rewrite(f2);

write('N=');

readln(n);

for i:=1 to n do

for j:=i+1 to n do begin

a[i,j]:=random(50)+1;a[j,i]:=a[i,j];

end;

smin:=maxint;

p(1,1);

close(f1);

writeln(f2,n);

for i:=1 to n do begin

for j:=1 to n-1 do

write(f2,a[i,j]:3);

writeln(f2,a[i,n]:3);

end;

writeln(f2,'-------------------');

for i:=1 to n-1 do write(f2,rez[i],' ' );

writeln(f2,rez[n] );

writeln(f2,smin);

close(f2);

end.