C++ :

/*
	author :hzoi_ztx
	title  :Ali的乐谱 
	ALG    :并茶几 
	comment:
	
	内存 16 Mb  =>  419 4304 int数组 
	[2014 10 19]
*/

#include <cstdio>
#include <algorithm>

#define  maxn  1002
#define  maxe  600000

struct edg{
	int u , v , w ;
} e[maxe] ; int tot = 0 ;

int n , K ;
int fa[maxn] = {0} ;

bool cmp(const edg a , const edg b) { return a.w < b.w ; }
int Find(int x) { return fa[x] ? fa[x] = Find(fa[x]) : x ; }
bool Union(int u , int v) {
	u = Find(u) ; v = Find(v) ;
	if (u == v) return false ;
	fa[u] = v ; return true ;
}

int main() {
	//#define  READ
	#ifdef   READ
		freopen("piano.in" ,"r",stdin ) ;
		freopen("piano.out","w",stdout) ;
	#endif
	int i , j , k ;
	scanf("%d%d", &K , &n ) ;
	for (i = 1 ; i <= n ; i ++ ) {
		for (j = 1 ; j <= i ; j ++ ) scanf("%*d") ;
		for (j = i+1 ; j <= n ; j ++ ) {
			scanf("%d", &k ) ;
			tot ++ ;
			e[tot].u = i ; e[tot].v = j ; e[tot].w = k ;
		}
	}
	
	std::sort(e+1 , e+tot+1 , cmp) ;
	
	int cnt = 0 ;
	
	for (i = 1 ; i <= tot ; i ++ ) {
		if (Union(e[i].u , e[i].v)) {
			cnt ++ ;
			if (cnt == n-K+1) {
				printf("%d\n", e[i].w ) ;
				#ifdef   READ
					fclose(stdin ) ;
					fclose(stdout) ;
				#endif
				return 0 ;
			}
		}
	}
	
	#ifdef   READ
		fclose(stdin ) ;
		fclose(stdout) ;
	#endif
	return 0 ;
}