HA31_Path(8)

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1000000000;

class Graph {
private:
    int N; // Количество вершин
    vector<vector<int> > adj;
    vector<vector<int> > weights;
    vector<int> dist;
    vector<bool> used;

public:
    Graph(int n) {
        N = n;
        adj.resize(N);
        weights.resize(N, vector<int>(N, -1));
        dist.resize(N, INF);
        used.resize(N, false);
    }

    void add_edge(int from, int to, int weight) {
        adj[from].push_back(to);
        if (weights[from][to] == -1 || weight < weights[from][to]) {
            weights[from][to] = weight;
        }
    }

    int dijkstra(int start_v, int end_v) {
        dist[start_v] = 0;

        for (int i = 0; i < N; ++i) {
            int v = -1;
            for (int j = 0; j < N; ++j) {
                if (!used[j] && (v == -1 || dist[j] < dist[v])) {
                    v = j;
                }
            }

            if (dist[v] == INF) {
                break;
            }

            used[v] = true;

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

                if (dist[v] + weight < dist[to]) {
                    dist[to] = dist[v] + weight;
                }
            }
        }

        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;
}