for(i=0 ; i<N ; i++) ut[i] = INTINF;
for(i=1 ; i<N ; i++) u[i] = INTINF;
s = 0;
u[s] = 0;

for(i=1 ; i<N ; i++){
	点sを始点とする枝(s,j)のそれぞれについて{
		L = u[s]+枝(s,j)の重み;
		if( u[j]==INTINF && ut[j] > L ) ut[j] = L;
	}
	int nMin = INTINF;
	for( j=1 ; j<N ; j++ ){
		if( nMin > ut[j] ){
			nMin = ut[j];
			s = j;
		}
	}
 	u[s] = ut[s]; //点sの最短経路長を確定
	ut[s] = INTINF
}