floyd.cpp

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

const int N = 105;

int n, m, q;
int dist[N][N], trace[N][N];

bool chmin(int &a, int b) {
  if (a > b) { a = b; return true; }
  return false;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q;
  memset(dist, 0x3f, sizeof(dist));
  for (int i = 1; i <= n; i++) {
    dist[i][i] = 0;
    trace[i][i] = i;
  }
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    if (chmin(dist[u][v], c)) {
      trace[u][v] = v;
    }
    if (chmin(dist[v][u], c)) {
      trace[v][u] = u;
    }
  }
  for (int k = 1; k <= n; k++)
  for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++) {
    if (chmin(dist[i][j], dist[i][k] + dist[k][j])) {
      trace[i][j] = trace[i][k];
    }
  }
  auto printTrace = [](int u, int v)->void {
    vector<int> vec;
    while (true) {
      vec.push_back(u);
      if (u == v) break;
      u = trace[u][v];
    }
    cout << vec.size() << ' ';
    for (int i = 0; i < (int) vec.size(); i++) {
      cout << vec[i] << " \n"[i + 1 == vec.size()];
    }
  };
  while (q--) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 0) {
      cout << dist[u][v] << '\n';
    }
    else {
      printTrace(u, v);
    }
  }
}