pb2 3/2/2021

#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <limits>
using namespace std;
const int NMAX = 103;
const int OO = numeric_limits<int>::max();
int n, m, k, disMin = OO, closest;
list<pair<int, int>> edges[NMAX];
int dis[NMAX];
struct QElem {
    int to, cost;
    QElem(int to, int cost) : to(to), cost(cost) {}
    bool operator < (const QElem &other) const noexcept {
        return this->cost > other.cost;
    }
};

void read() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back(make_pair(b, c));
    }
}

void dijkstra() {
    priority_queue<QElem> q;
    q.push(QElem(k, 0));
    dis[k] = 0;
    while (!q.empty()) {
        int node = q.top().to;
        q.pop();
        for (auto it : edges[node]) {
            auto [to, cost] = it;
            if (dis[to] > dis[node] + cost) {
                dis[to] = dis[node] + cost;
                q.push(QElem(to, dis[to]));
            }
        }
    }
}

void solveA() {
    cout << "Orase accesibile: ";
    for (int i = 1; i <= n; i++) {
        if (dis[i] != OO) {
            cout << i << ' ';
        }
        if (i != k && disMin > dis[i]) {
            disMin = dis[i];
            closest = i;
        }
    }
    cout << endl;
}

void dfs(int node, int cdis, list<int> road, int nrc) {
    if (dis[node] == cdis) {
        for (int it : road) {
            cout << it << ' ';
        }
        cout << endl;
    }
    if (nrc == 4) {
        cout << "oras aflat la distanta 3" << node << "dis:" << dis[node] << endl;
    }
    for (auto it : edges[node]) {
        auto [to, cost] = it;
        road.push_back(to);
        dfs(to, cdis + cost, road, nrc + 1);
    }
}

int main() {
    read();
    fill(dis + 1, dis + n + 1, OO);
    dijkstra();
    solveA();
    cout << "cel mai apropiat oras: " << closest << endl;
    cout << "drumuri: " << endl;
    dfs(k, 0, {k}, 0);
    return 0;
}