package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type NodeKey int

func newNode(key NodeKey) *Node {
	node := Node{
		key:    key,
		degree: 0,
		mark:   false,
	}
	node.left = &node
	node.right = &node
	return &node
}

type Node struct {
	key    NodeKey
	degree int
	mark   bool

	graphNode *DirectedGraphNode

	parent *Node
	left   *Node
	right  *Node
	child  *Node
}

func (node *Node) getAllChildlen() []*Node {
	children := []*Node{}
	child := node.child
	if node.child != nil {
		for {
			children = append(children, child)
			child = child.right
			if child == node.child {
				break
			}
		}
	}
	return children
}

func (node *Node) insertLeft(newNode *Node) {
	oldLeft := node.left
	node.left = newNode
	node.left.right = node
	newNode.left = oldLeft
	newNode.left.right = newNode
}

func (node *Node) insertRight(r *Node) {
	oldRight := node.right
	node.right = r
	node.right.left = node
	r.right = oldRight
	r.right.left = r
}

func (node *Node) reset() {
	node.degree = 0
	node.parent = nil
	node.child = nil
	node.left = nil
	node.right = nil
	node.mark = false
}

func (p *Node) appendChild(c *Node) {
	if p.child == nil {
		c.left = c
		c.right = c
		p.child = c
	} else {
		firstChild := p.child
		secondChild := p.child.right

		// firstChild <---> c <---> secondChild
		firstChild.right = c
		c.left = firstChild
		c.right = secondChild
		secondChild.left = c
	}
	c.parent = p
	p.degree++
}

func (p *Node) deleteChild(c *Node) *Node {
	if c.right == c {
		p.child = nil
	} else {
		oldLeft := c.left
		oldRight := c.right
		oldLeft.right = oldRight
		oldRight.left = oldLeft
		p.child = c.left
	}
	p.degree--

	return c
}

func (node *Node) preorderTreeWalk() string {
	s := fmt.Sprintf("(%v", node.key)
	c := node.child
	for c != nil {
		s += " " + c.preorderTreeWalk()
		c = c.right
		if c == node.child {
			break
		}
	}
	s += ")"
	return s
}

func (node *Node) getAllBrothers() []*Node {
	brothers := []*Node{node}
	current := node.right
	for current != node {
		brothers = append(brothers, current)
		current = current.right
	}
	return brothers
}

var infty int = 2 * 1000000000

func newFibonacciHeap() *FibonacciHeap {
	heap := FibonacciHeap{}
	heap.minimum = nil
	heap.nNodes = 0
	return &heap
}

// FibonacciHeap is an implementation of CLRS sec. 13
type FibonacciHeap struct {
	minimum *Node
	nNodes  int
}

func (heap *FibonacciHeap) insert(x *Node) {
	x.reset()
	if heap.minimum == nil {
		heap.minimum = x
		x.left = x
		x.right = x
	} else {
		heap.minimum.insertLeft(x)
		if x.key < heap.minimum.key {
			heap.minimum = x
		}
	}
	heap.nNodes++
}

func (heap *FibonacciHeap) getMinimum() *Node {
	return heap.minimum
}

func (heap *FibonacciHeap) extractMinimum() *Node {
	minimum := heap.minimum
	if minimum != nil {
		for _, child := range minimum.getAllChildlen() {
			heap.appendRootNode(child)
		}
		minimum.child = nil

		minimum.right.left = minimum.left
		minimum.left.right = minimum.right

		if minimum == minimum.right {
			heap.minimum = nil
		} else {
			heap.minimum = minimum.right
			heap.consolidate()
		}
		heap.nNodes--
	}
	return minimum
}

func (heap *FibonacciHeap) appendRootNode(node *Node) {
	node.parent = nil
	heap.minimum.insertLeft(node)
}

func (heap *FibonacciHeap) consolidate() {
	maxDegree := int(math.Ceil(math.Log2(float64(heap.nNodes)) / math.Log2(1.61803)))
	degrees := make([]*Node, maxDegree+2)

	for _, root := range heap.minimum.getAllBrothers() {
		x := root
		d := x.degree
		for d < len(degrees) && degrees[d] != nil {
			y := degrees[d]
			if x.key > y.key {
				tmp := x
				x = y
				y = tmp
			}
			heap.linkRootElements(y, x)
			degrees[d] = nil
			d++
		}
		degrees[d] = x
	}
	heap.minimum = nil
	for _, node := range degrees {
		if node != nil {
			if heap.minimum == nil {
				node.left = node
				node.right = node
				heap.minimum = node
			} else {
				heap.minimum.insertRight(node)
				if node.key < heap.minimum.key {
					heap.minimum = node
				}
			}
		}
	}
}

func (heap *FibonacciHeap) deleteNodeFromRoots(target *Node) *Node {
	if target.parent != nil {
		panic("target is not a root element")
	}

	if target == target.right {
		heap.minimum = nil
	} else {
		target.right.left = target.left
		target.left.right = target.right
		target.left = nil
		target.right = nil
	}

	return target
}

func (heap *FibonacciHeap) linkRootElements(child, parent *Node) {
	heap.deleteNodeFromRoots(child)
	parent.appendChild(child)
	child.mark = true
}

func (this *FibonacciHeap) unionWith(other *FibonacciHeap) {
	if this.minimum == nil {
		this.minimum = other.minimum
	} else {
		this.minimum.insertRight(other.minimum)
		if other.minimum != nil && other.minimum.key < this.minimum.key {
			this.minimum = other.minimum
		}
	}
	this.nNodes += other.nNodes
}

func (heap *FibonacciHeap) decreaseKey(target *Node, keyNew NodeKey) *Node {
	if keyNew > target.key {
		panic("new key is larger than the current key")
	}

	target.key = keyNew
	parent := target.parent
	if parent != nil && target.key < parent.key {
		heap.cut(target, parent)
		heap.cascadingCut(parent)
	}
	// fmt.Println(target, heap.minimum)
	if heap.minimum == nil || target.key < heap.minimum.key {
		heap.minimum = target
	}

	return target
}

func (heap *FibonacciHeap) cut(c, p *Node) {
	p.deleteChild(c)
	heap.appendRootNode(c)
	c.parent = nil
	c.mark = false
}

func (heap *FibonacciHeap) cascadingCut(target *Node) {
	parent := target.parent
	if parent != nil {
		if target.mark {
			heap.cut(target, parent)
			heap.cascadingCut(parent)
		} else {
			target.mark = true
		}
	}
}

func (heap *FibonacciHeap) delete(target *Node) *Node {
	heap.decreaseKey(target, NodeKey(-infty))
	deletedElement := heap.extractMinimum()
	return deletedElement
}

func (heap *FibonacciHeap) print() {
	root := heap.minimum
	if root == nil {
		return
	}
	fmt.Println(heap.nNodes)
	for {
		fmt.Print(root.key, ":", root.preorderTreeWalk(), "\n")
		root = root.right
		if root == heap.minimum {
			break
		}
	}
}

type DirectedGraphNodeID int

type DirectedGraphNode struct {
	key         DirectedGraphNodeID
	heapNode    *Node
	adjacents   []*DirectedGraphNode
	costs       []int
	distance    int
	predecessor *DirectedGraphNode
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]*DirectedGraphNode, nNodes)
	for i := 0; i < nNodes; i++ {
		node := DirectedGraphNode{}
		node.key = DirectedGraphNodeID(i)
		node.distance = infty
		graph.nodes[i] = &node
	}
	return &graph
}

type DirectedGraph struct {
	nodes []*DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(i, j DirectedGraphNodeID, cost int) {
	g.nodes[i].adjacents = append(g.nodes[i].adjacents, g.nodes[j])
	g.nodes[i].costs = append(g.nodes[i].costs, cost)
}

func (g *DirectedGraph) print() {
	for i := 0; i < len(g.nodes); i++ {
		node := g.nodes[i]
		key := node.key
		strings := []string{strconv.Itoa(int(key)), strconv.Itoa(node.distance)}
		for j := 0; j < len(node.adjacents); j++ {
			nodeJ := fmt.Sprintf("(%v, %v)", node.adjacents[j].key, node.costs[j])
			strings = append(strings, nodeJ)
		}
		fmt.Printf("%v\n", strings)
	}
}

func (g *DirectedGraph) relaxEdge(l, r *DirectedGraphNode, w int) {
	if r.distance < l.distance+w {
		panic("original distance is shorter than new distance")
	}
	r.distance = l.distance + w
	r.predecessor = l
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	nEdges := nextInt()
	startNode := DirectedGraphNodeID(nextInt())

	graph := newDirectedGraph(nNodes)

	for i := 0; i < nEdges; i++ {
		iNode := DirectedGraphNodeID(nextInt())
		jNode := DirectedGraphNodeID(nextInt())
		cost := nextInt()
		graph.setAdjacency(iNode, jNode, cost)
	}

	// Dijkstra algorithm
	graph.nodes[startNode].distance = 0
	heap := newFibonacciHeap()
	for _, graphNode := range graph.nodes {
		heapNode := newNode(NodeKey(infty))
		heapNode.graphNode = graphNode
		graphNode.heapNode = heapNode
		heap.insert(heapNode)
	}
	graph.nodes[startNode].heapNode.key = NodeKey(0)
	heap.minimum = graph.nodes[startNode].heapNode

	for heap.nNodes > 0 {
		nodeLeft := heap.extractMinimum().graphNode
		for iAdjacent := 0; iAdjacent < len(nodeLeft.adjacents); iAdjacent++ {
			nodeRight := nodeLeft.adjacents[iAdjacent]
			cost := nodeLeft.costs[iAdjacent]

			// heap.print()
			if nodeLeft.distance+cost < nodeRight.distance {
				heap.decreaseKey(nodeRight.heapNode, NodeKey(nodeLeft.distance+cost))
				graph.relaxEdge(nodeLeft, nodeRight, cost)
			}
		}
	}

	// graph.print()

	for iNode := 0; iNode < len(graph.nodes); iNode++ {
		node := graph.nodes[iNode]
		if node.distance >= infty {
			fmt.Println("INF")
		} else {
			fmt.Println(node.distance)
		}
	}
}



Measured memory_bytes: 60460