CSES - Graph Paths II | Đường đi đồ thị II

View as PDF



Author:
Problem types
Points: 1700 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Consider a directed weighted graph having \(n\) nodes and \(m\) edges. Your task is to calculate the minimum path length from node \(1\) to node \(n\) with exactly \(k\) edges.

Input

  • The first input line contains three integers \(n, m\) and \(k\): the number of nodes and edges, and the length of the path. The nodes are numbered \(1,2,\dots,n\).

Then, there are m lines describing the edges. Each line contains three integers \(a, b\) and \(c\): there is an edge from node \(a\) to node \(b\) with weight \(c\).

Output

  • Print the minimum path length. If there are no such paths, print −1.

Constraints

  • \(1\leq n\leq 100\)
  • \(1\leq m\leq n(n−1)\)
  • \(1\leq k\leq 10^9\)
  • \(1\leq a,b\leq n\)
  • \(1\leq c\leq 10^9\)

Example

Sample input

3 4 8
1 2 5
2 3 4
3 1 1
3 2 2

Sample output

27


Comments

There are no comments at the moment.