#include<bits/stdc++.h> using namespace std; const int maxi=0x7ffff; int f[105][105],w[101][101],f1[105][105]; int N,a,b,c,M,start,stop; int main() { cin>>N>>M; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { w[i][j]=maxi; } } for (int i=1;i<=M;i++) { cin>>a>>b>>c; w[a][b]=c; } cin>>start>>stop; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { f1[i][j]=f[i][j]=w[i][j]; } } for (int k=1;k<=N;k++) { for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { if ((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j])) f[i][j]=f[i][k]+f[k][j]; } } } for (int k=N;k>=1;k--) { for (int i=N;i>=1;i--) { for (int j=N;j>=1;j--) { if ((i!=j)&&(i!=k)&&(j!=k)&&(f1[i][k]+f1[k][j]<f1[i][j])) f1[i][j]=f1[i][k]+f1[k][j]; } } } cout<<f[start][stop]+f1[stop][start]; return 0; }