#include <queue>

#include <functional>

#define pp pair<int,int>

int solution(const vector<int> &A, const vector<int> &B, const vector<int> &C, const vector<int> &D) {

    // write your code in C++98

    int N = A.size();

    int M = D.size();

    vector<vector<int> > graph;

    graph.resize(M);

    for (int i = 0; i < M; i++) {

        graph[i].resize(M, -1);

    }

    for (int i = 0; i < N; i++) {

        graph[A[i]][B[i]] = (graph[A[i]][B[i]] == -1 ? C[i] : min(graph[A[i]][B[i]], C[i]));

        graph[B[i]][A[i]] = (graph[B[i]][A[i]] == -1 ? C[i] : min(graph[B[i]][A[i]], C[i]));

    }

    vector<int> dist(M, -1);

    priority_queue<pp, vector<pp>, greater<pp> > que;

    que.push(make_pair(0, 0));

    while (!que.empty()) {

        pp p = que.top();

        que.pop();

        if (dist[p.second] == -1) {

            dist[p.second] = p.first;

        }

        else {

            continue;

        }

        if (p.first <= D[p.second]) return p.first;

        for (int i = 0; i < graph[p.second].size(); i++) {

            if (graph[p.second][i] != -1) {

                que.push(make_pair(graph[p.second][i] + p.first, i));

            }

        }

    }

    return -1;

}