#include <string>
#include <vector>

using namespace std;

vector<vector<vector<int>>> n_fares;
vector<vector<int>> v_list;
vector<vector<int>> ch_list_;
int c_list_min;
int c_list_min_;
vector<vector<int>> c_list_min_sum;
int asdf;

struct info {
    int coordinate;
    int cost;
    
    info() : coordinate(0), cost(0) {}

    info(int c, int co) : coordinate(c), cost(co) {}
};

vector<vector<info>> list;

int ch_list(int k, int n){
    int i;
    int ch_list_min=0;
    int ch_list_max=list[k].size()-1;
    int ch_now=ch_list_max/2;
    while(ch_list_min<ch_list_max){
        if(list[k][ch_now].cost>n){
            ch_list_max=ch_now-1;
            ch_now=(ch_list_max+ch_list_min)/2;
        }else if(list[k][ch_now].cost<n){
            ch_list_min=ch_now+1;
            ch_now=(ch_list_max+ch_list_min)/2;
        }
    }
    if(list[k][ch_now].cost<n)
        return ch_now;
    else
        return ch_now-1;
}

void v_list_update(int k, int ch, int n){
    int i;
    for(i=0;i<v_list[k].size();i++){
        if(v_list[k][i]>ch && (v_list[k][i]<v_list[k][n] || v_list[k][n]==-1))
        {
            v_list[k][i]++;
            if(k==0 && n==1)
                asdf++;
        }
    }
    v_list[k][n]=ch+1;
}

void list_update(int k, int ch, int ch_){//sab,집어넣을 위치, 뺄 위치
    int i;
    info a=list[k][ch_];
    for(i=ch_;i>ch+1;i--){
        list[k][i]=list[k][i-1];
    }
    list[k][ch+1]=a;
}

void push_list_(int k, int n){//sab, 조사할 list 순서
    int i,ch;
    //asdf=n_fares[0][list[k][n].coordinate].size();
    int n_=list[k][n].coordinate;
    for(i=0;i<n_fares[1][n_].size();i++){
        if(v_list[k][n_fares[1][n_][i]] > -1){//이미 리스트에 있을 경우
            if(list[k][n].cost+n_fares[0][n_][i]<list[k][v_list[k][n_fares[1][n_][i]]].cost){
                ch=ch_list(k,list[k][n].cost+n_fares[0][n_][i]);
                list[k][v_list[k][n_fares[1][n_][i]]].cost=list[k][n].cost+n_fares[0][n_][i];
                list_update(k,ch,v_list[k][n_fares[1][n_][i]]);
                v_list_update(k,ch, n_fares[1][n_][i]);
                continue;
            }
            continue;
        }
        ch=ch_list(k,list[k][n].cost+n_fares[0][n_][i]);
        list[k].insert(list[k].begin() + ch+1, {n_fares[1][n_][i],list[k][n].cost+n_fares[0][n_][i]});
        v_list_update(k,ch,n_fares[1][n_][i]);
    }
    //if(list[k][])
}

int ch_end(int n){
    int i;
    for(i=0;i<3;i++){
        if(n>=list[i].size())
            break;
        ch_list_[i+1][list[i][n].coordinate]=list[i][n].cost;
        ch_list_[0][list[i][n].coordinate]++;
        if(ch_list_[0][list[i][n].coordinate]==2){
            ch_list_[4][list[i][n].coordinate]=ch_list_[1][list[i][n].coordinate]+ch_list_[2][list[i][n].coordinate]+ch_list_[3][list[i][n].coordinate];
            if(ch_list_[4][list[i][n].coordinate] < c_list_min){
                //if(asdf==0)
                    //asdf=ch_list_[4][list[i][n].coordinate];
                c_list_min=ch_list_[4][list[i][n].coordinate];
                //asdf=list[2][0].coordinate;
            }
        }
        if(c_list_min<=((ch_list_[1][list[i][n].coordinate]==-1) ? list[0][list[0].size()-1].cost : ch_list_[1][list[i][n].coordinate])
           +((ch_list_[2][list[i][n].coordinate]==-1) ? list[1][list[1].size()-1].cost : ch_list_[2][list[i][n].coordinate])
           +((ch_list_[3][list[i][n].coordinate]==-1) ? list[2][list[2].size()-1].cost : ch_list_[3][list[i][n].coordinate]))
            return 1;
    }
    return 0;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    asdf=0;
    int answer = 0,i;
    n_fares.resize(2, vector<vector<int>>(n, vector<int>(0,0)));//0==값 1==도착지
    list.resize(3, vector<info>());
    v_list.resize(3,vector<int>(n,-1));
    ch_list_.resize(5,vector<int>(n,-1));
    c_list_min=2147483647;
    c_list_min_=0;
    c_list_min_sum.resize(3,vector<int>(n,717483647));
    
    
    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);
    }

    list[0].push_back({s-1,0});
    list[1].push_back({a-1,0});
    list[2].push_back({b-1,0});

    v_list[0][s-1]=0;
    v_list[1][a-1]=0;
    v_list[2][b-1]=0;
    
    //return n_fares[1][list[0][0].coordinate][0];
    //return n_fares[0][list[0][0].coordinate].size();
    
    //if(b!=6) return 0;
    for(i=0;i<n;i++){
        push_list_(0,i);
        push_list_(1,i);
        push_list_(2,i);
        if(ch_end(i))
            break;
            
    }
    
    //return asdf;
    //return v_list[0][0]*100000+v_list[0][1]*10000+v_list[0][2]*1000+v_list[0][3]*100+v_list[0][4]*10+v_list[0][5];
    //return list[0][2].cost;
    return c_list_min;
}