#include <string>
#include <vector>

using namespace std;

int answer;
int min_;
int history=0;
vector<vector<vector<int>>> n_fares;
vector<vector<vector<int>>> list;
vector<vector<int>> count;

int update_list(int k, int n)//시작점, 길이
{
    int i,j,l, min1=0,ch;
    long min2=list[k][1][n-1]+1000000;
    int sum=list[k][1][n-1];
    for(i=0;i<n;i++){
        for(j=0;j<n_fares[1][list[k][0][i]].size();j++){
            ch=0;
            for(l=0;l<n;l++){
                if(n_fares[1][list[k][0][i]][j]==list[k][0][l])// && list[k][1][i]+n_fares[0][list[k][0][i]][j]>list[k][1][l])
                {
                    ch=1;
                    break;
                }
            }
            if(ch==1) continue;
            if(min2>list[k][1][i]+n_fares[0][list[k][0][i]][j]){
                min2=list[k][1][i]+n_fares[0][list[k][0][i]][j];
                min1=n_fares[1][list[k][0][i]][j];
            }
        }
    }
    list[k][0].push_back(min1);
    list[k][1].push_back(min2);
    ch=0, sum=0;
    for(i=0;i<count[0].size();i++){
        if(count[0][i]==list[k][0][list[k][1].size()-1]){
            ch++;
            count[k+1][i]=list[k][1][list[k][1].size()-1];
            count[4][i]+=list[k][1][list[k][1].size()-1]-list[k][1][list[k][1].size()-2];
            if(count[1][i]>-1 && count[2][i]>-1 && count[3][i]>-1){
                if(count[4][i]<min_)
                    min_=count[4][i];
            }
        }
        if(count[k+1][i]<0){
            count[4][i]+=list[k][1][list[k][1].size()-1]-list[k][1][list[k][1].size()-2];
        }
        if(min_>count[4][i])
                sum=1;
    }
    if(ch==0){
        count[0].push_back(list[k][0][list[k][1].size()-1]);
        count[1].push_back(-1);
        count[2].push_back(-1);
        count[3].push_back(-1);
        count[4].push_back(list[0][1][list[0][0].size()-1]+list[1][1][list[1][0].size()-1]+list[2][1][list[2][0].size()-1]);
        count[k+1][count[k+1].size()-1]=list[k][1][list[k][1].size()-1];
    }
    if(sum){
        return 0;
    }
    return 1;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    answer = 0;
    history=0;
    min_=2147483647;
    int i,j,k,exit=1, sum;
    vector<int> ch(0,0);
    n_fares.resize(2, vector<vector<int>>(n, vector<int>(0,0)));//0==값 1==도착지,
    list.resize(3, vector<vector<int>>(2, vector<int>(0,0)));// A/B/C,비용/지점, 길이
    count.resize(5, vector<int>(0, 0));// 0=지점 1=a값 2=b값 3=c값 4=합계 5=완성유무
    
    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;
                }
            }
        }
    }*/
    answer=0;
    list[0][0].push_back(s-1);
    list[1][0].push_back(a-1);
    list[2][0].push_back(b-1);
    list[0][1].push_back(0);
    list[1][1].push_back(0);
    list[2][1].push_back(0);
    
    count[0].push_back(s-1);
    count[0].push_back(a-1);
    count[0].push_back(b-1);
    for(i=0;i<3;i++){
        count[1].push_back(-1);
        count[2].push_back(-1);
        count[3].push_back(-1);
        count[4].push_back(0);
        count[i+1][i]=0;
    }

    while(exit && n>=list[0][0].size()){
        for(i=0;i<3;i++){
            if(update_list(i,list[i][0].size()))
                exit=0;
        }
        exit++;
    }
    return min_;
}