clc;
clear;
A=importdata('kcenter5.txt');

n=A(1,1);  % number of vertices
m=A(1,2);  % number of edges
k=A(1,3);  % number of centers

D=zeros(n,n);  % this allocation is not needed but is much more efficient (about a factor 5 in running time in this case!) 

for i=2:m+1
   D(A(i,1),A(i,2))=A(i,3);
   D(A(i,2),A(i,1))=A(i,3);
end

D= graphallshortestpaths(sparse(D));

S=zeros(1,k);   	% S is the set of centers
S(1)=1;         		% Take 1 as first center (or take one at random) 
    
Dist2centers=D(S(1),:);  % Dist2centers(i) is the distance from i to S
tic
for i=2:k
    [MaxDist,S(i)]=max(Dist2centers);           % S(i) is the point at maximum distance and will be the next center. The var MaxDist is not used here.
	Dist2centers=min(Dist2centers,D(S(i),:));   % Update the distances to the centers
end
toc

MaxDist=max(Dist2centers)