dijkstra

#include<iostream>

using namespace std;
#define INF 1000000000
#define MAX 10000
int G[MAX][MAX], c[MAX][MAX], U[MAX],
p[MAX], d[MAX], n, m, r;


void dijkstra(int r)
{
    int v, w, min, i, j;
    for (i = 1; i <= n; i++) { U[i] = 0; p[i] = r; d[i] = INF; }
    d[r] = p[r] = 0;
    for (i = 1; i <= n; i++)
    {
        v = 0; min = INF;
        for (j = 1; j <= n; j++)
            if (U[j] == 0 && d[j] < min) { v = j; min = d[j]; }
        U[v] = 1;
        for (j = 1; j <= G[v][0]; j++)
        {
            w = G[v][j];
            if (U[w] == 0 && d[v] + c[v][w] < d[w])
            {
                d[w] = d[v] + c[v][w]; p[w] = v;
            }
        }
    }
}

int main() {

    int u, v, w, i, j;
    scanf_s("%d %d %d", &n, &m, &r);
    for (i = 1; i <= n; i++) {
        G[i][0] = 0;
        for (j = 1; j <= n; j++) {
            c[i][j] = INF;
            if (i == j)c[i][j] = 0;
        }
    }
    for (i = 1; i <= m; i++) {
        scanf_s("%d %d %d", &u, &v, &w);
        G[u][++G[u][0]] = v;
        G[v][++G[v][0]] = u;
        c[u][v] = c[v][u] = w;
    }
    dijkstra(r);
    for (i = 1; i <= n; i++) {
        printf("%d %d\n", i, d[i]);
    }
    return 0;


}