1196_F. K-th Path_28552
You are given a connected undirected weighted graph consisting of n vertices and m edges.

You need to print the k-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).

More formally, if d is the matrix of shortest paths, where d_{i, j} is the length of the shortest path between vertices i and j (1 ≤ i < j ≤ n), then you need to print the k-th element in the sorted array consisting of all d_{i, j}, where 1 ≤ i < j ≤ n.

Input

The first line of the input contains three integers n, m and k (2 ≤ n ≤ 2 ⋅ 10^5, n - 1 ≤ m ≤ min\Big((n(n-1))/(2), 2 ⋅ 10^5\Big), 1 ≤ k ≤ min\Big((n(n-1))/(2), 400\Big) — the number of vertices in the graph, the number of edges in the graph and the value of k, correspondingly.

Then m lines follow, each containing three integers x, y and w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10^9, x ≠ y) denoting an edge between vertices x and y of weight w.

It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices x and y, there is at most one edge between this pair of vertices in the graph).

Output

Print one integer — the length of the k-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).

Examples

Input


6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5


Output


3


Input


7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1


Output


9
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.AbstractCollection;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cunbidun
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Task1196F solver = new Task1196F();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task1196F {
        private static final long INFLL = (long) 9e18 + 7;
        private InputReader in;
        private OutputWriter out;
        private ArrayList<PairII>[] adj;
        private ArrayList<Long> list = new ArrayList<>();
        private TreeSet<PairII> set = new TreeSet<>();
        private ArrayList<TripIII> edgeList = new ArrayList<>();
        private long[] d;
        private int n;
        private int k;
        private long cur;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            this.in = in;
            this.out = out;
            n = in.nextInt();
            int m = in.nextInt();
            k = in.nextInt();
            adj = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
            for (int i = 1; i <= m; i++) {
                int u = in.nextInt();
                int v = in.nextInt();
                int w = in.nextInt();
                edgeList.add(new TripIII(w, u, v));
            }
            Collections.sort(edgeList);
            for (int i = 0; i < MaxMin.Min(k, m); i++) {
                int u = edgeList.get(i).second;
                int v = edgeList.get(i).third;
                int w = edgeList.get(i).first;
                adj[u].add(new PairII(w, v));
                adj[v].add(new PairII(w, u));
            }
            d = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                d[i] = INFLL;
            }
            cur = INFLL;
            int i;
            for (i = 1; i <= n; i++) {
                dijkstra(i);
                if (list.size() > k) break;
            }

            Collections.sort(list);
            cur = list.get(k - 1);
            list.subList(k, list.size()).clear();
            i++;

            for (; i <= n; i++) {
                dijkstra(i);
                Collections.sort(list);
                list.subList(k, list.size()).clear();
                cur = list.get(k - 1);
            }


            out.println(cur);
        }

        private void dijkstra(int start) {
            //adj: PairII (first distance, second vertex)
            PriorityQueue<PairLI> pq = new PriorityQueue<>(); // can be changed to PairII.
            d[start] = 0;
            ArrayList<Integer> pos = new ArrayList<>();
            pq.add(new PairLI(0, start));
            pos.add(start);
            int cnt = 0;
            while (!pq.isEmpty()) {
                int u = pq.peek().second;
                long du = pq.peek().first;
                pq.poll();
                if (du > d[u]) continue;

                PairII tmp = new PairII(MaxMin.Min(start, u), MaxMin.Max(start, u));
                if (cnt != 0 && du < cur && !set.contains(tmp)) {
                    list.add(du);
                    set.add(tmp);
                }
                cnt++;
                if (cnt > k || du >= cur) {
                    for (int i : pos) d[i] = INFLL;
                    return;
                }
                for (PairII p : adj[u]) {
                    int v = p.second;
                    long uv = p.first;
                    if (d[v] > du + uv) {
                        d[v] = du + uv;
                        pos.add(v);
                        pq.add(new PairLI(d[v], v));
                    }
                }
            }
            for (int i : pos) d[i] = INFLL;
        }

    }

    static class PairII implements Comparable<PairII> {
        public int first;
        public int second;

        public PairII(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            PairII pair = (PairII) o;

            return first == pair.first && second == pair.second;
        }

        public String toString() {
            return "(" + first + "," + second + ")";
        }

        public int compareTo(PairII o) {
            int value = Integer.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            return Integer.compare(second, o.second);
        }

    }

    static class TripIII implements Comparable<TripIII> {
        public int first;
        public int second;
        public int third;

        public TripIII(int first, int second, int third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            TripIII trip = (TripIII) o;

            return first == trip.first && second == trip.second && third == trip.third;
        }

        public String toString() {
            return "(" + first + "," + second + "," + third + ")";
        }

        public int compareTo(TripIII o) {
            int value = Integer.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            value = Integer.compare(second, o.second);
            if (value != 0) {
                return value;
            }
            return Integer.compare(third, o.third);
        }

    }

    static class PairLI implements Comparable<PairLI> {
        public long first;
        public int second;

        public PairLI(long first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            PairLI pair = (PairLI) o;

            return first == pair.first && second == pair.second;
        }

        public String toString() {
            return "(" + first + "," + second + ")";
        }

        public int compareTo(PairLI o) {
            int value = Long.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            return Integer.compare(second, o.second);
        }

    }

    static class OutputWriter {
        private final PrintWriter out;

        public OutputWriter(OutputStream outputStream) {
            out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.out = new PrintWriter(writer);
        }

        public void close() {
            out.close();
        }

        public void println(long i) {
            out.println(i);
        }

    }

    static class InputReader extends InputStream {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class MaxMin {
        public static <T extends Comparable<T>> T Max(T x, T y) {
            T max = x;
            if (y.compareTo(max) > 0) max = y;
            return max;
        }

        public static <T extends Comparable<T>> T Min(T x, T y) {
            T min = x;
            if (y.compareTo(min) < 0) min = y;
            return min;
        }

    }
}


7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
 6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5
 2 1 1
1 2 123456789
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1000000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
27 28 1000000000
 8 7 19
1 2 1000000000
2 3 999999999
3 4 999999998
4 5 999999997
5 6 999999996
6 7 999999995
7 8 999999994
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
27 28 1000000000
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 12
2 1 1
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
20 28 1000000000
 8 7 19
1 2 1000000000
2 3 999999999
3 4 999999998
4 5 999999997
5 7 999999996
6 7 999999995
7 8 999999994
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000100000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
27 28 1000000000
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
1 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 15
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 2
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1010000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
20 28 1000000000
 8 7 19
1 3 1000000000
2 3 999999999
3 4 999999998
4 5 999999997
5 7 999999996
6 7 999999995
7 8 999999994
 8 7 19
1 3 1000000000
2 3 999999999
3 4 999999998
4 5 154063658
5 7 999999996
6 7 999999995
7 8 999999994
 8 7 19
1 3 1000000000
2 3 999999999
3 5 1713603821
4 5 154063658
5 7 999999996
6 7 999999995
7 8 999999994
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 8
3 7 9
4 1 8
2 1 1
 8 7 19
1 4 1000000000
2 3 999999999
3 4 999999998
4 5 154063658
5 7 999999996
6 7 999999995
7 8 999999994
 8 7 19
1 4 1000000000
2 3 999999999
3 4 999999998
4 5 84933160
5 7 999999996
6 7 999999995
7 8 215677923
 8 7 19
1 4 1000000001
2 3 999999999
3 4 999999998
4 5 84933160
5 7 999999996
6 7 999999995
7 8 215677923
 8 7 19
1 2 1000000001
2 3 999999999
3 4 999999998
4 5 84933160
5 7 999999996
6 7 999999995
7 8 215677923
 8 7 19
1 2 1000000001
2 3 999999999
3 4 999999998
4 5 114797370
5 7 999999996
6 7 999999995
7 8 215677923
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
3 27 1000000000
20 28 1000000000
 8 7 16
1 2 1000000000
2 3 999999999
3 4 999999998
4 5 999999997
5 7 999999996
6 7 999999995
7 8 999999994
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1010000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1010000000
20 28 1000000000
 8 7 19
1 3 1000000000
2 3 999999999
3 6 999999998
4 5 999999997
5 7 999999996
6 7 999999995
7 8 999999994
 8 7 19
1 3 1000000000
2 3 999999999
2 5 1713603821
4 5 154063658
5 7 999999996
6 7 999999995
7 8 999999994
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 12
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 15
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 1 8
5 3 6
2 5 5
3 7 9
4 1 12
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 1 8
5 3 6
2 5 5
3 7 9
4 1 20
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 4
1 6 4
7 1 6
7 2 1
4 3 2
3 1 8
5 3 6
2 5 5
3 7 9
4 1 20
2 1 1
 7 15 18
2 6 6
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 1 8
5 3 6
2 5 5
3 7 9
4 1 20
2 1 1
 8 7 19
1 3 1000000000
2 3 999999999
3 5 999999998
4 5 154063658
5 7 999999996
6 7 999999995
7 8 999999994
 28 27 378
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1010000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000100000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
27 28 1000000000
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 4
1 6 4
7 1 3
7 2 1
4 3 2
3 1 8
5 3 6
2 5 5
3 7 9
4 1 20
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 3
3 2 2
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
 8 7 19
1 3 1000000000
2 3 999999999
3 5 999999998
4 5 154063658
5 7 999999996
6 7 545546123
7 8 999999994
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 8
1 6 4
7 1 6
7 2 1
4 3 3
3 2 2
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
 8 7 19
1 4 1000000000
2 3 999999999
3 4 999999998
4 5 154063658
5 7 999999996
6 7 999999995
7 8 215677923
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 1
3 7 9
4 1 12
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 18
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 1 2
5 3 6
2 5 5
3 7 9
4 1 12
2 1 1
 7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 3
3 2 2
5 3 6
2 5 5
3 7 9
6 1 8
2 1 1

9
 3
 123456789
 27000000000
 3999999982
 27010000000
 10
 26010000000
 2999999997
 27010100000
 17
 6
 26020000000
 2999999994
 2154063655
 2867667478
 9
 2154063654
 2084933156
 2084933157
 2300611077
 2330475287
 25010000000
 2999999988
 26030000000
 2999999989
 3713603811
 10
 10
 10
 10
 10
 10
 2154063655
 27010100000
 10
 6
 2154063655
 6
 2154063654
 9
 6
 6
