Link to this code:
https://cses.fi/paste/95edef498f482b844137d0/
#include<bits/stdc++.h>
using namespace std;
typedef long long int lln;
typedef long long ll;
#define R for (auto i = 0; i < n; ++i)
#define V for(auto &val : v)
#define pb push_back
const double pi = 3.14159265358979323846;
#define debug(x) cout<< #x << ' ' << x <<endl
#define inf -1
const long long int N = 500;
long long int dist[N][N];
void shortest_dist(long long int n)
{
for(long long int k=0;k<n;k++)
{
for(long long int i=0;i<n;i++)
{
for(long long int j=0;j<n;j++)
{
if(dist[i][k] == -1 || dist[k][j] == -1) continue;
if(dist[i][j] == -1) {
dist[i][j] = dist[i][k] + dist[k][j];
}else{
dist[i][j] = min(dist[i][j] , dist[i][k]+dist[k][j]);
}
}
}
}
}
void solve()
{
/* No Proof <-> No Submission */
long long int n,m,q;
cin >> n >> m >> q;
for(long long int i=0;i<n;i++)
{
for(long long int j=0;j<n;j++)
{
dist[i][j]=-1;
}
}
for(long long int i=0;i<m;i++)
{
long long int x,y,len;
cin >> x >> y >> len;
x--,y--;
if(dist[x][y] == -1){
dist[x][y] = len;
dist[y][x] = len;
}else{
dist[x][y] = min(dist[x][y] , len);
dist[y][x] = min(dist[y][x] , len);
}
}
shortest_dist(n);
for(long long int i=0;i<q;i++)
{
long long int x,y;
cin >> x >> y;
cout << dist[x-1][y-1] << endl;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
long long int t=1;
// cin >> t;
while(t--){solve();}
return 0;
}