#include <iostream>
#include <list>
#include <queue>
#include <fstream>
#include <limits>
#include <algorithm>
#include <iomanip>
using namespace std;
struct node
{
    int to,
        length;
    node(int _to, int _length)
    {
        to = _to;
        length = _length;
    }
};
const int INF = INT_MAX;
list <node>* graph;
bool* visited;
int* dist;
queue <int> width;

void dij(int v, int n);
void print(int n);

int main()
{
    const int INF = INT_MAX;
    int n, v, w, l;
    ifstream in("input.txt");
    in >> n;
    graph = new list<node>[n];
    visited = new bool[n];
    dist = new int[n];

    if (in.is_open())
        while (!in.eof())
        {
            in >> v >> w >> l;
            if (--v < n && --w < n)
                graph[v].push_back(node(w, l));
        }
    in.close();

    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        visited[i] = false;
    }

    int startV;
    cin >> startV;
    dist[--startV] = 0;
    dij(startV, n);
    system("pause");
    return 0;
}

void dij(int v, int n)
{
    for each (node x in graph[v])
    {
        dist[x.to] = min(dist[x.to], dist[v] + x.length);
        if (!visited[x.to])
            width.push(x.to);
    }
    print(n);
    visited[v] = true;
    if (!width.empty())
    {
        int t = width.front();
        width.pop();
        dij(t, n);
    }
}

void print(int n)
{
    cout << setw(6) << "\nVertex" << setw(6) << "Dist" << endl;
    for (int i = 0; i < n; i++)
        if(dist[i] == INF)
            cout << setw(6) << i + 1 << setw(6) << "INF" << endl;
        else
            cout << setw(6) << i + 1 << setw(6) << dist[i] << endl;
}