#include <string>
#include <vector>

using namespace std;

vector<vector<vector<int>>> n_fares;
vector<vector<int>> v_list;
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]=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 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));
    
    
    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);
    }
    
    return asdf;
    return v_list[0][1];
    return list[0][5].cost;
}