#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n,m,s;
int book[N],dis[N];
struct node {
    int v,w;
};
vector<node>e[N];
void dijkstra() {
    for (int i=1;i<=n;i++)dis[i] = 2147483647;
    dis[s] = 0;
    for (int i=1;i<n;i++) {
        int minn = 2147483647,id=0;
        for (int j=1;j<=n;j++) {
            if (dis[j]<minn && book[j]==0) {
                minn = dis[j];
                id = j;
            }
        }
        book[id] = 1;
        for (int i=0;i<e[id].size();i++) {
            int v = e[id][i].v;
            int w = e[id][i].w;
            if (dis[v]>dis[id]+w) {
                dis[v] = dis[id]+w;
            }
        }
    }
}
int main() {
    cin>>n>>m>>s;
    for (int i=1;i<=m;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
    }
    dijkstra();
    for (int i=1;i<=n;i++)cout<<dis[i]<<" ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 55005;
int n,m,s;
int dis[N],book[N];
struct node {
    int v,w;
};
vector<node>e[N];
void dijkstra() {
    for (int i=1;i<=n;i++)dis[i]=2147483647;
    dis[1] = 0;
    for (int i=1;i<n;i++) {
        int minn = 2147483647,id=0;
        for (int j=1;j<=n;j++) {
            if (dis[j]<minn && book[j]==0) {
                minn = dis[j];
                id = j;
            }
        }
        book[id] = 1;
        for (int i=0;i<e[id].size();i++) {
            int v = e[id][i].v;
            int w = e[id][i].w;
            if (dis[v]>dis[id]+w) {
                dis[v] = dis[id]+w;
            }
        }
    }
}
int main() {
    cin>>n>>m>>s;
    for (int i=1;i<=m;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    dijkstra();
    while (s--) {
        int x,y;
        cin>>x>>y;
        cout<<dis[x]+dis[y]<<endl;
    }
    return 0;
}