HA31_Paths(9)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1000000000;

class Edge {
public:
    int to;
    int weight;
    Edge(int t, int w) {
        to = t;
        weight = w;
    }
};

class Graph {
private:
    int N;
    vector<vector<Edge> > adj;
    vector<int> dist;
    vector<bool> used;

public:
    Graph(int n) {
        N = n;
        adj.resize(N);
        dist.resize(N, INF);
        used.resize(N, false);
    }

    void add_edge(int from, int to, int weight) {
        adj[from].push_back(Edge(to, weight));
    }

    int dijkstra(int start_v, int end_v) {
        dist[start_v] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        pq.push(make_pair(0, start_v));

        while (!pq.empty()) {
            pair<int, int> p = pq.top();
            pq.pop();
            int v = p.second;
            int d = p.first;

            if (used[v]) {
                continue;
            }
            used[v] = true;

            if (v == end_v) {
                return dist[end_v];
            }

            for (size_t i = 0; i < adj[v].size(); ++i) {
                int to = adj[v][i].to;
                int weight = adj[v][i].weight;

                if (dist[v] + weight < dist[to]) {
                    dist[to] = dist[v] + weight;
                    pq.push(make_pair(dist[to], to));
                }
            }
        }

        if (dist[end_v] == INF) {
            return -1;
        } else {
            return dist[end_v];
        }
    }
};

int main() {
    int N, M;
    cin >> N >> M;

    int S, F;
    cin >> S >> F;
    S--;
    F--;

    Graph graph(N);

    for (int i = 0; i < M; ++i) {
        int A, B, T;
        cin >> A >> B >> T;
        A--;
        B--;
        graph.add_edge(A, B, T);
    }

    int result = graph.dijkstra(S, F);
    cout << result << endl;

    return 0;
}