L - Walking to School

#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using i64 = long long;

const int INF = 0x3f3f3f3f;

int n, m, T;
vector<vector<ii>> gr;

i64 dijkstra(int source) {
  vector<i64> dist(n+1, INF);

  dist[source] = 0;

  priority_queue<tuple<i64, i64, int>> pq;
  pq.push({ 0, 0, source });

  while (!pq.empty()) {
    auto [d, r, u] = pq.top(); pq.pop();

    if (d > dist[u]) continue;

    for (auto [w, to] : gr[u]) {
      if (dist[u] + r * w < dist[to]) {
        dist[to] = dist[u] + r * w;

        pq.push({ dist[to], r + (w == 0 ? 0 : 1), to });
      }
    }
  }

  return dist[T] == INF ? -1 : dist[T];
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> T, --T;

  gr.assign(n, vector<ii>());

  for (int i = 0; i < m; ++i) {
    int a, b, c; cin >> a >> b >> c, --a, --b;

    gr[a].push_back({ c, b });
    gr[b].push_back({ c, a });
  }

  cout << dijkstra(0) << '\n';
}