#include <string>
#include <vector>

using namespace std;

int history=0;
int history_=0;
vector<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_fares[0][start].size();i++){
        if(n_fares[0][start][i]==0) continue;
        if(i==fin){
            update_(count+n_fares[0][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[0][start][i])){
            count__(n,n_fares[1][start][i],fin, count+n_fares[0][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_fares[0][start].size();i++){
        if(n_fares[0][start][i]==0) continue;
        if(i==fin){
            list.push_back(i);
            update(count+n_fares[0][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[0][start][i]))
            count_(n,n_fares[1][start][i],fin, count+n_fares[0][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,j,k;
    n_fares.resize(2, vector<vector<int>>(n, vector<int>(0,0)));
    
    for(i=0;i<fares.size();i++){
        n_fares[0][fares[i][0]-1].push_back(fares[i][2]);
        n_fares[0][fares[i][1]-1].push_back(fares[i][2]);
        n_fares[1][fares[i][0]-1].push_back(fares[i][1]-1);
        n_fares[1][fares[i][1]-1].push_back(fares[i][0]-1);
    }

    for(i=0;i<n_fares[0].size();i++){
        for(j=n_fares[0][i].size()-1;j>=0;j--){
            for(k=j-1;k>=0;k--){
                if(n_fares[0][i][j]<n_fares[0][i][k]){
                    answer=n_fares[0][i][j];
                    n_fares[0][i][j]=n_fares[0][i][k];
                    n_fares[0][i][k]=answer;
                    
                    answer=n_fares[1][i][j];
                    n_fares[1][i][j]=n_fares[1][i][k];
                    n_fares[1][i][k]=answer;
                }
            }
        }
    }
    count_(n,a-1,b-1, 0,s-1);
    return history;
}