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.*;
import java.math.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.util.Comparator.*;

public class Main {
    FastScanner in;
    PrintWriter out;
    boolean multitests = false;
    long mod = (long) 1e9 + 7; // 998_244_353L || (long) 1e9 + 9
    ArrayList<Integer>[] graph;
    ArrayList<GraphPair>[] weightedGraph;

    private void solve() throws IOException {
        // solveA();
        // solveB();
        // solveC();
        // solveD();
        // solveE();
        solveF();
    }

    private void solveA() throws IOException {
        long[] a = in.nextLongArray(3);
        out.println(sumLong(a) / 2);
    }

    private void solveB() throws IOException {
        int n = in.nextInt(), k = in.nextInt();
        long[] a = in.nextLongArray(n);
        int[] ans = new int[k];
        int s = 0;
        long sum = sumLong(a);
        for (int i = 0; i < n && s < k - 1; i++) {
            if (a[i] % 2 == 1)
                ans[s++] = i + 1;
            sum -= a[i];
        }
        if (sum % 2 == 1)
            ans[s++] = n;
        out.println(s == k ? "YES" : "NO");
        if (s == k) {
            for (int i : ans)
                out.print(i + " ");
            out.println();
        }
    }

    private void solveC() throws IOException {
        int n = in.nextInt();
        int maxX = (int) 1e5, minX = -(int) 1e5;
        int maxY = (int) 1e5, minY = -(int) 1e5;
        for (int i = 0; i < n; i++) {
            int x = in.nextInt(), y = in.nextInt();
            if (in.nextInt() == 0)
                minX = max(minX, x);
            if (in.nextInt() == 0)
                maxY = min(maxY, y);
            if (in.nextInt() == 0)
                maxX = min(maxX, x);
            if (in.nextInt() == 0)
                minY = max(minY, y);
        }
        out.println(minX <= maxX && minY <= maxY ? "1 " + minX + " " + minY : "0");
    }

    private void solveD() throws IOException {
        int n = in.nextInt(), k = in.nextInt();
        char[] s = in.next().toCharArray(), t = "RGB".toCharArray();
        int ans = k;
        for (int i = 0; i < t.length; i++) {
            int[] pref = new int[n];
            for (int j = 0; j < n; j++)
                pref[j] = (j == 0 ? 0 : pref[j - 1]) + (s[j] == t[(i + j) % 3] ? 0 : 1);
            for (int j = k - 1; j < n; j++)
                ans = min(ans, pref[j] - (j < k ? 0 : pref[j - k]));
        }
        out.println(ans);
    }

    private void solveE() throws IOException {
        int b = in.nextInt(), w = in.nextInt();

        if (min(b, w) * 3 + 1 < max(b, w)) {
            out.println("NO");
            return;
        }

        out.println("YES");

        int sx = 3, sy = w > b ? 1 : 2;
        if (w < b) {
            int orange = w;
            w = b;
            b = orange;
        }

        if (w > b) {
            int x = sx, y = sy;
            out.println(x + " " + y);
            w--;
            while (w > b) {
                y++;
                out.println(x + " " + y);
                b--;
                out.println(x - 1 + " " + y);
                out.println(x + 1 + " " + y);
                w -= 2;
                if (w > b) {
                    y++;
                    out.println(x + " " + y);
                    w--;
                }
            }
        }

        if (w != b)
            b = 1 / 0;

        int x = sx, y = sy;
        while (b > 0) {
            x++;
            out.println(x + " " + y);
            x++;
            out.println(x + " " + y);
            b--;
        }
    }

    class Triplet implements Comparable<Triplet> {
        long dist;
        int start, finish;

        public Triplet(int start, int finish, long dist) {
            this.start = start;
            this.finish = finish;
            this.dist = dist;
        }

        @Override
        public int compareTo(Triplet o) {
            return dist != o.dist ? Long.compare(dist, o.dist) :
                    finish != o.finish ? Integer.compare(finish, o.finish) :
                            Integer.compare(start, o.start);
        }
    }

    private void solveF() throws IOException {
        int n = in.nextInt(), m = in.nextInt(), k = in.nextInt() * 2;
        weightedGraph = in.nextWeightedGraph(n, m, false);

        TreeMap<Long, Long> used = new TreeMap<>();
        TreeSet<Triplet> next = new TreeSet<>();

        for (int v = 0; v < n; v++) {
            sort(weightedGraph[v]);

            for (GraphPair u : weightedGraph[v]) {
                if ((next.size() < k || next.last().dist > u.w)) {
                    long mask = ((long) v << 30) + u.v;
                    if (!used.containsKey(mask)) {
                        if (next.size() == k) {
                            Triplet t = next.pollLast();
                            used.remove(((long) t.start << 30) + t.finish);
                        }
                        used.put(mask, u.w);
                        next.add(new Triplet(v, u.v, u.w));
                    }
                } else
                    break;
            }
        }

        while (k-- > 1) {
            Triplet cur = next.pollFirst();
            // out.println(cur.start + " " + cur.finish + " " + cur.dist);
            for (GraphPair u : weightedGraph[cur.finish]) {
                if (cur.start == u.v) continue;
                if ((next.size() < k || next.last().dist > cur.dist + u.w)) {
                    long mask = ((long) cur.start << 30) + u.v;
                    if (!used.containsKey(mask)) {
                        if (next.size() == k) {
                            Triplet t = next.pollLast();
                            used.remove(((long) t.start << 30) + t.finish);
                        }
                        used.put(mask, cur.dist + u.w);
                        next.add(new Triplet(cur.start, u.v, cur.dist + u.w));
                    } else if (used.get(mask) > cur.dist + u.w) {
                        next.remove(new Triplet(cur.start, u.v, used.get(mask)));
                        used.put(mask, cur.dist + u.w);
                        next.add(new Triplet(cur.start, u.v, cur.dist + u.w));
                    }
                } else
                    break;
            }
        }
        // out.println(next.first().start + " " + next.first().finish + " " + next.first().dist);
        out.println(next.pollFirst().dist);
    }

    void shuffleInt(int[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void shuffleLong(long[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            long swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void reverseInt(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    void reverseLong(long[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            long swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    int maxInt(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    long maxLong(long[] a) {
        long max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    int minInt(int[] a) {
        int min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long minLong(long[] a) {
        long min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long sumInt(int[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

    long sumLong(long[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long binpowmod(long a, long n) {
        long res = 1;
        a %= mod;
        n %= mod - 1;
        while (n > 0) {
            if (n % 2 == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            n /= 2;
        }
        return res;
    }

    class GraphPair implements Comparable<GraphPair> {
        int v;
        long w;

        GraphPair(int v, long w) {
            this.v = v;
            this.w = w;
        }

        public int compareTo(GraphPair o) {
            return w != o.w ? Long.compare(w, o.w) : Integer.compare(v, o.v);
        }
    }

    ArrayList<Integer>[] createGraph(int n) throws IOException {
        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    ArrayList<GraphPair>[] createWeightedGraph(int n) throws IOException {
        ArrayList<GraphPair>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s), 32768);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextInt();
            return a;
        }

        int[][] nextIntTable(int n, int m) throws IOException {
            int[][] a = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextInt();
            return a;
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextLong();
            return a;
        }

        long[][] nextLongTable(int n, int m) throws IOException {
            long[][] a = new long[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextLong();
            return a;
        }

        ArrayList<Integer>[] nextGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<Integer>[] graph = createGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                graph[v].add(u);
                if (!directed)
                    graph[u].add(v);
            }
            return graph;
        }

        ArrayList<GraphPair>[] nextWeightedGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<GraphPair>[] graph = createWeightedGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                long w = in.nextLong();
                graph[v].add(new GraphPair(u, w));
                if (!directed)
                    graph[u].add(new GraphPair(v, w));
            }
            return graph;
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        for (int t = multitests ? in.nextInt() : 1; t-- > 0; )
            solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}