import heapq

def dijkstra(V, edges, start):
    adj = [[] for _ in range(V)]
    for u, v, wt in edges:
        adj[u].append((v, wt))
        adj[v].append((u, wt))

    pq = []
    distances = [float('inf')] * V
    visited = [False] * V

    distances[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        current_distance, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True

        for v, weight in adj[u]:
            if not visited[v] and current_distance + weight < distances[v]:
                distances[v] = current_distance + weight
                heapq.heappush(pq, (distances[v], v))

    return distances

if __name__ == "__main__":
    V = int(input("Enter the number of vertices: "))
    E = int(input("Enter the number of edges: "))
    edges = []

    print("Enter each edge as 'u v weight':")
    for _ in range(E):
        u, v, wt = map(int, input().split())
        edges.append((u, v, wt))

    start = int(input("Enter the starting vertex: "))
    result = dijkstra(V, edges, start)
    print("The shortest distances from the starting vertex are:")
    for i, d in enumerate(result):
        print(f"Vertex {i}: {d}")