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
//package Contest575div3;


import javafx.util.Pair;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class mainF {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter = new FastScanner(System.in);
    public static int kk;
    public static void main(String[] args) throws IOException {
        int n=enter.nextInt();
        int m=enter.nextInt();
        kk=enter.nextInt();
        triple[] arr=new triple[m];
        for (int i = 0; i <m ; i++) {
            int a=enter.nextInt();
            int b=enter.nextInt();
            Long w=enter.nextLong();
            arr[i]=new triple(w, a,b);
        }

        sortMergeNoRecursive(arr, 0, arr.length, triple.class,triple::compareTo);
        HashSet<Integer> hashSet=new HashSet<>();
        for (int i = 0; i <Math.min(m,kk) ; i++) {
            hashSet.add(arr[i].a);
            hashSet.add(arr[i].b);
        }
        int a[]=new int[3*(int)1e5];
        int s=1;
        for (int h:hashSet
                ) {
            a[h]=s;
            s++;
        }

        Graph g= new Graph(hashSet.size(), Math.min(m,kk));

        for (int i = 0; i <Math.min(m,kk) ; i++) {
            g.add(a[arr[i].a], a[arr[i].b], arr[i].w);
            g.add(a[arr[i].b], a[arr[i].a], arr[i].w);
        }
        g.solve();

    }

    static class triple implements Comparable<triple>{
        long w;
        int a;
        int b;

        public triple(long w, int a, int b) {
            this.w = w;
            this.a = a;
            this.b = b;
        }

        @Override
        public int compareTo(triple o) {
            return Long.compare(w,o.w);
        }
    }

    public static <T>  void sortMergeNoRecursive(T[] arr, int first, int last, Class<T> c, Comparator<T> comparator) {
        int len = last;
        int n = 1; // кратность сравнений (сравнивать по 1-му элем., 2-м ...)
        int shift; // сдвиг в перебираемом массиве
        int two_size; // количество элементов для 2-го массива
        T[] arr2;
        while (n < len) {
            shift = first;
            while (shift < len) {
                if (shift + n >= len) break;
                two_size = (shift + n * 2 > len) ? (len - (shift + n)) : n;
                arr2 = merge(Arrays.copyOfRange(arr, shift, shift + n),
                        Arrays.copyOfRange(arr, shift + n, shift + n + two_size),c,comparator);
                for (int i = 0; i < n + two_size; ++i)
                    arr[shift + i] = arr2[i]; // замена на отсортированное
                shift += n * 2;
            }
            n *= 2;
        }
    }

    public static <T> T[] merge(T[] arr_1, T[] arr_2,Class<T> c , Comparator<T> comparator) {
        int len_1 = arr_1.length, len_2 = arr_2.length;
        int a = 0, b = 0, len = len_1 + len_2; // a, b - счетчики в массивах
        //T[] result = new <>[len];
        T[] result=(T[]) Array.newInstance(c,len);


        for (int i = 0; i < len; i++) {
            if (b < len_2 && a < len_1) {
                if (comparator.compare(arr_1[a], arr_2[b]) > 0) result[i] = arr_2[b++];
                else result[i] = arr_1[a++];
            } else if (b < len_2) {
                result[i] = arr_2[b++];
            } else {
                result[i] = arr_1[a++];
            }
        }
        return result;
    }




    //and others on mccme

    static class Graph {
        int n; //vertex
        int m; //edges
        LinkedList<Integer>[] vert; //adjacency list
        long[] len;
        int[] from ;
        PriorityQueue<Integer> queue;
        ArrayList<Long> arr;
        //ArrayList<Pair<Integer, Integer>> edge; //edges in graph
        HashMap<Pair<Integer,Integer>,Long> ed;
        boolean used[]; //massives for veteces
        static class pair{
            int u,w;
            public pair(int u, int w) {
                this.u = u;
                this.w = w;
            }
        }

        public Graph(int n) {
            this.n = n;
            vert = new LinkedList[n + 1]; //1 ,...., n
            for (int i = 1; i < n + 1; i++) vert[i] = new LinkedList<>();
            used = new boolean[n + 1];
            ed=new HashMap<>();
        }

        public Graph(int n, int m) {
            this.n = n;
            from = new int[n + 1];
            len = new long[n + 1];
            queue = new PriorityQueue<>(Comparator.comparingLong(c -> len[c]));
            vert = new LinkedList[n + 1]; //1 ,...., n
            for (int i = 1; i < n + 1; i++) vert[i] = new LinkedList<>();
            //edge = new ArrayList<>(); //0 ,...., m-1
            used = new boolean[n + 1];
            ed=new HashMap<>();
            arr=new ArrayList<>();
        }

        public void add(int a, int b) {
            vert[a].addLast(b);
            /*if (edge != null) {
                edge.add(new Pair<>(a, b));
            }*/
        }
        public void add(int a, int b, long w) {
            vert[a].addLast(b);
            /*if (edge != null) {
                edge.add(new Pair<>(a, b));
            }*/
            ed.put(new Pair(a,b),w);
        }

        public void min_path(int a) { //Diikstra
            queue.clear();
            Arrays.fill(len,Long.MAX_VALUE );
            Arrays.fill(from,0);
            Arrays.fill(used, false);
            len[a] = 0;
            //our queue of verteces

            queue.add(a);
            int s;
            while (queue.size() != 0) {
                s = queue.poll();
                if(used[s]) continue;
                for (Integer n : vert[s]) {
                    if (!used[n]) {
                        len[n] = Math.min(len[n], len[s] + ed.get(new Pair(s, n)));
                        queue.add(n);
                    }
                }
                if(s!=a) arr.add(len[s]);
                used[s] = true;
            }
        }
        public  void solve(){
            HashSet<Integer> hash=new HashSet<>();
            for (Pair<Integer, Integer> par:ed.keySet()) {
                hash.add(par.getKey());
                hash.add( par.getValue());
            }


            ArrayList<Integer> arrayList=new ArrayList<>(hash);

            for (int i = 0; i <arrayList.size() ; i++) {
                    min_path(arrayList.get(i));
            }
            Long sort_arr[]=new Long[4*(int)1e5];
            for (int i = 0; i <arr.size() ; i++) {
                sort_arr[i]=arr.get(i);
            }
            sortMergeNoRecursive(sort_arr,0,arr.size(), Long.class, Long::compareTo);
            System.out.println(sort_arr[2*kk-2]);

        }

        public int n_components() {
            int ans = 0;
            TreeSet<Integer> vis = new TreeSet<>();
            for (int i = 1; i < n + 1; i++) vis.add(i);
            while (!vis.isEmpty()) {
                BFS(vis.first(), vis);
                ans++;
            }
            return ans;

        }

        public void check_bipartite() {//we need to check every component in graph on bipartite
            int[] colores = new int[n + 1];
            TreeSet<Integer> vis = new TreeSet<>();
            for (int i = 1; i < n + 1; i++) vis.add(i);
            Arrays.fill(used, false);
            while (!vis.isEmpty()) {
                int s = vis.first();
                LinkedList<Integer> queue = new LinkedList<>();//our queue of verteces
                used[s] = true;
                colores[s] = 1;
                queue.add(s);
                vis.remove(s);
                while (queue.size() != 0) {
                    s = queue.poll();
                    for (Integer n : vert[s]) {
                        if (!used[n]) {
                            used[n] = true;
                            colores[n] = 3 - colores[s];
                            queue.add(n);
                            vis.remove(n);
                        } else if (colores[n] == colores[s]) {
                            System.out.println("NO");
                            return;
                        }
                    }
                }
            }
            System.out.println("YES");
            for (int i = 1; i < n + 1; i++) System.out.print((colores[i] == 1) ? i + " " : ""); // first share of graph
        }
        public long[][] dist_matrix(){//Floyd(O(V^3))
            long mat[][][]=new long[n+1][n+1][n+1];
            for (int i = 1; i <n+1 ; i++) {
                for (int j = 1; j <n+1 ; j++) {
                    Object tmp=ed.get(new Pair<>(i,j));
                    mat[i][j][0]=(null == ed.get(new Pair<>(i,j)) ) ? Integer.MAX_VALUE: (long)tmp;
                    // mat[i][j][0]=(matrix[i][j]==-1 || i==j) ? Integer.MAX_VALUE : matrix[i][j];
                }
            }
            for (int k = 1; k <n+1 ; k++) {
                for (int i = 1; i <n+1 ; i++) {
                    for (int j = 1; j <n+1 ; j++) {
                        mat[i][j][k]=Math.min(mat[i][j][k-1], mat[i][k][k-1]+ mat[k][j][k-1]);
                    }
                }
            }
            long ans[][]=new long[n+1][n+1];
            for (int i = 1; i <n+1 ; i++) {
                for (int j = 1; j <n+1 ; j++) {
                    ans[i][j]=mat[i][j][n];
                }
            }
            return ans;
        }

        public void check_tree() {//check_our graph on tree
            int s = 1, v = 0;
            LinkedList<Integer> queue = new LinkedList<>();//our queue of verteces
            Arrays.fill(used, false);
            used[s] = true;
            queue.add(s);
            while (queue.size() != 0) {
                s = queue.poll();
                v++;
                int tmp = vert[s].size();
                for (Integer n : vert[s]) {
                    if (!used[n]) {
                        used[n] = true;
                        queue.add(n);
                        tmp--;
                    }
                }
                if (tmp >= 2) {
                    System.out.println("NO");
                    return;
                }
            }
            if (v == n) System.out.println("YES");
            else System.out.println("NO");
        } //check our graph on tree

        public void BFS(int s, TreeSet<Integer> vis) {
            LinkedList<Integer> queue = new LinkedList<>();//our queue of verteces
            Arrays.fill(used, false);
            used[s] = true;
            vis.remove(s);
            queue.add(s);
            while (queue.size() != 0) {
                s = queue.poll();
                for (Integer n : vert[s]) {
                    if (!used[n]) {
                        used[n] = true;
                        vis.remove(n);
                        queue.add(n);
                    }
                }
            }
        }

        public void BFS(int s) {
            LinkedList<Integer> queue = new LinkedList<>();//our queue of verteces
            Arrays.fill(used, false);
            used[s] = true;
            queue.add(s);
            while (queue.size() != 0) {
                s = queue.poll();
                out.print(s + " ");
                for (Integer n : vert[s]) {
                    if (!used[n]) {
                        used[n] = true;
                        queue.addLast(n);
                    }
                }
            }
        }

        public void DFS_no_rec(int s) {
            LinkedList<Integer> queue = new LinkedList<>();//our queue of verteces
            Arrays.fill(used, false);
            used[s] = true;
            queue.add(s);
            while (queue.size() != 0) {
                s = queue.poll();
                out.print(s + " ");
                for (Integer n : vert[s]) {
                    if (!used[n]) {
                        used[n] = true;
                        queue.addFirst(n);
                    }
                }
            }
        }
        void diametr_tree(){
            //Заводим Массив dist в начале и берем любую вершину i в дереве и ищем от неё макс расттояние (в точке k достикается) (с помощью DFS)
            //Дальше - берем и от этой вершины находим максимаальное расстояние (в точке j достигается)- это наш диаметр (путь j<->k)
        }



        void DFSUtil(int v, boolean was[]) {
            was[v] = true;
            Iterator<Integer> i = vert[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!was[n]) {
                    DFSUtil(n, was);
                }
            }
        }

        void DFS(int v) {
            boolean was[] = new boolean[n + 1];
            DFSUtil(v, was);
        }

        public void cout_tree() {
            for (int i = 1; i < n + 1; i++) {
                out.println(i + " ");
                out.println(vert[i]);
            }
        }


    }




    static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

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

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

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

        char nextChar() throws IOException {
            return (char) (br.read());
        }

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

