#include <string>
#include <vector>

using namespace std;

int history=0;
int history_=0;
vector<vector<int>> n_fares;
vector<int> list;
vector<int> list_;

int answer;

void update_(int n){
    if(history_==0) history_=n;
    if(history_>n) history_=n;
}

void count__(int n, int start, int fin, int count){
    list_.push_back(start);
    int ch=0;
    for(int i=0;i<n;i++){
        if(n_fares[start][i]==0) continue;
        if(i==fin){
            update_(count+n_fares[start][i]);
        }
        ch=0;
        for(int j=0;j<list_.size();j++)
            if(list_[j]==i){
                ch++;
                break;
            }
        if(ch==0 && (history_==0 || history_>count+n_fares[start][i])){
            count__(n,i,fin, count+n_fares[start][i]);
        }
    }
    list_.pop_back();
}

void update(int n,int end, int s,int nn){
    int ch=0,i;
    for(i=0;i<list.size();i++){
        if(list[i]==s){
            ch++;
            break;
        }
    }
    if(ch==0){
        for(i=0;i<list.size();i++){
            history_=0;
            count__(nn,s,list[i], 0);
            if(ch==0) ch=history_;
            if(history_<ch) ch=history_;
        }
    }else{
        ch=0;
    }
    if(history==0) history=n+ch;
    if(history>n+ch) history=n+ch;
}

void count_(int n, int start, int fin, int count, int s){
    list.push_back(start);
    int ch=0;
    for(int i=0;i<n;i++){
        if(n_fares[start][i]==0) continue;
        if(i==fin){
            list.push_back(i);
            update(count+n_fares[start][i],fin,s,n);
            list.pop_back();
        }
        ch=0;
        for(int j=0;j<list.size();j++)
            if(list[j]==i){
                ch++;
                break;
            }
        if(ch==0 && (history==0 || history>count+n_fares[start][i]))
            count_(n,i,fin, count+n_fares[start][i],s);
    }
    list.pop_back();
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    answer = 0;
    history=0;
    int i;
    n_fares.resize(n, vector<int>(n,0));
    for(i=0;i<fares.size();i++){
        n_fares[fares[i][0]-1][fares[i][1]-1]=fares[i][2];
        n_fares[fares[i][1]-1][fares[i][0]-1]=fares[i][2];
    }
    
    count_(n,a-1,b-1, 0,s-1);
    return history;
}