package main

import (
    "bufio"
    "os"
    "fmt"
    "strconv"
    "container/heap"
)

const INF = 1000000000000000

/*********** PriorityQueue ***********/
type PriorityQueue struct {
    arr []interface{}
    comps []CompFunc
}
/*
p < q ... -1
p == q ... 0
p > q ...  1
*/
type CompFunc func(p, q interface{}) int

func NewPriorityQueue() *PriorityQueue {
    return new(PriorityQueue)
}

func (pq PriorityQueue) Len() int {
    return len(pq.arr)
}

func (pq PriorityQueue) Swap(i, j int) {
    pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
}

func (pq PriorityQueue) Less(i, j int) bool{
    for _, comp := range pq.comps {
        result := comp(pq.arr[i], pq.arr[j])
        switch result {
            case -1: return true
            case 1:  return false
            case 0:  continue
        }
    }
    return true
}

func (pq *PriorityQueue) Push(x interface{}) {
    pq.arr = append(pq.arr, x)
}

func (pq *PriorityQueue) Pop() interface{} {
    n := pq.Len()
    item := pq.arr[n - 1]
    pq.arr = pq.arr[:n - 1]
    return item
}

func (pq *PriorityQueue) IsEmpty() bool {
    return pq.Len() == 0
}



/* for dijkstra */
/* type Edge */
type Edge struct {
    to int
    cost int
}

/* type State */
type State struct {
    score int
    node int
}

/* type Graph */
type Graph struct {
    starts []State
    edges [][]Edge
    size int
    comps []CompFunc
    defaultScore int
}

func dijkstra(graph *Graph) []int {
    score := make([]int, graph.size)
    for i := 0; i < graph.size; i++ {
        score[i] = graph.defaultScore
    }
    que := new(PriorityQueue)
    que.comps = graph.comps
    for _, start := range graph.starts {
        score[start.node] = start.score
        heap.Push(que, start)
    }
    //visited := make([]bool, graph.size)
    for !que.IsEmpty() {
        state := heap.Pop(que).(State)
        //visited[state.node] = true
        for _, edge := range graph.edges[state.node] {
            //if visited[edge.to] {
            //    continue
            //}
            newScore := state.score + edge.cost
            if score[edge.to] > newScore {
                score[edge.to] = newScore
                heap.Push(que, State{score: newScore, node: edge.to})
            }
        }
    }
    return score
}

/* input */
var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}


/* Test by AOJ */
/* AOJ GRL_1_A Shortest Path - Single Scource Shortest Path */
func main() {
    sc.Split(bufio.ScanWords)
    v, e, r := readInt(), readInt(), readInt()
    edges := make([][]Edge, v)
    for i := 0; i < e; i++ {
        s, t, d := readInt(), readInt(), readInt()
        edges[s] = append(edges[s], Edge{to: t, cost:d})
    }

    var starts []State
    starts = append(starts, State{score: 0, node: r})

    var comp CompFunc
    comp = func(p, q interface{}) int {
        if p.(State).score < q.(State).score {
            return -1
        } else if p.(State).score == q.(State).score {
            return 0
        } else {
            return 1
        }
        return 0
    }
    var comps []CompFunc
    comps = append(comps, comp)

    graph := new(Graph)
    graph.edges = edges
    graph.starts = starts
    graph.size = v
    graph.defaultScore = INF
    graph.comps = comps

    dist := dijkstra(graph)
    
    wrt := bufio.NewWriter(os.Stdout)
    for i := 0; i < v; i++ {
        d := dist[i]
        if d == INF {
            fmt.Fprintln(wrt, "INF")
        } else {
            fmt.Fprintln(wrt, d)
        }
    }
    wrt.Flush()
}


Measured memory_bytes: 24460