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

public class CF1196F extends PrintWriter {
	CF1196F() { super(System.out, true); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1196F o = new CF1196F(); o.main(); o.flush();
	}

	static class E {
		int i, j;
		long w;
		E(int i, int j, long w) {
			if (i > j) {
				int tmp = i; i = j; j = tmp;
			}
			this.i = i; this.j = j; this.w = w;
		}
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		int M = Math.max(m, k * (k + 1) / 2);
		E[] ee = new E[M];
		for (int h = 0; h < m; h++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			int w = sc.nextInt();
			ee[h] = new E(i, j, w);
		}
		Arrays.sort(ee, 0, m, (e, f) -> Long.signum(e.w - f.w));
		m = Math.min(m, k);
		for (int l = 0; 1 << l < n; l++) {
			int m_ = m;
			for (int a = 0; a < m; a++) {
				E e = ee[a];
				for (int b = a + 1; b < m; b++) {
					E f = ee[b];
					int i = -1, j = -1;
					if (e.i == f.i) {
						i = e.j; j = f.j;
					} else if (e.i == f.j) {
						i = e.j; j = f.i;
					} else if (e.j == f.i) {
						i = e.i; j = f.j;
					} else if (e.j == f.j) {
						i = e.i; j = f.i;
					}
					if (i != j)
						ee[m_++] = new E(i, j, e.w + f.w);
				}
			}
			Arrays.sort(ee, 0, m_, (e, f) -> e.i != f.i ? e.i - f.i : e.j != f.j ? e.j - f.j : Long.signum(e.w - f.w));
			m = 0;
			for (int a = 0; a < m_; a++)
				if (a == 0 || ee[a].i != ee[a - 1].i || ee[a].j != ee[a - 1].j)
					ee[m++] = ee[a];
			Arrays.sort(ee, 0, m, (e, f) -> Long.signum(e.w - f.w));
			m = Math.min(m, k);
		}
		println(ee[k - 1].w);
	}
}
