Código em java maluco

Eu estou tentando resolver um exercício que está nesse link aqui: https://br.spoj.com/problems/REDOTICA/

Eu fiz um algoritmo para isso, porém não está retornando o que deveria.
O teste que eu fiz que retornou os valores errados, foi com os seguintes valores:
n2=3
m3=3
vet[0][0]=1 ; vet[0][1]=2 ; vet[0][2]=10
vet[1][0]=1 ; vet[1][1]=2 ; vet[1][2]=10
vet[2][0]=1 ; vet[2][1]=2 ; vet[2][2]=10

Era para retornar no final:
Teste 1 Menor!!!: 20
2 3
3 1

Porém, por alguma razão está retornando:
Teste 1 Menor!!!: 20
1 2
2 3
3 1

Eu tentei resolver o problema da questão da seguinte maneira:
criei a função caminho() para fazer todas as combinações possíveis de conjunto de caminhos diretos entre duas vilas. Depois criei a função verificar() para verificar se esses caminhos são válidos. Na função caminho(), a cada combinação achada, ela vai chamar a função verificar() para saber se essa combinação é válida, ou seja, se essa combinação consegue conectar todas as vilas entre si.

Coloquei vários System.out.println() para facilitar na identificação do erro e percebi que o vetmenor[] (vetor que guarda combinação de caminhos válida que causa menos danos ao meio ambiente) em um certo momento do código, acha a combinação certa que é:
vetmenor[]=[ 0, 1 ,1 ]

Mas logo depois ele muda o vetmenor[] para vetmenor[]=[ 1, 1, 1]. Sendo que eu marquei com System.out.println todos as linhas logo antes dos comandos que mudam o valor desse vetor e em nenhum momento depois do vetmenor[] assumir os valores vetmenor[]=[ 0, 1, 1], esses System.out.println foram acionados. Logo não tem como o vetmenor ter mudado de vetmenor[]=[ 0, 1, 1] para vetmenor[]=[ 1, 1, 1]. Porém isso aconteceu. Talvez eu não tenha marcado todos os momentos em que o vetmenor[] muda de valor com System.out.println(), já que isso está acontecendo. E todos os momentos em que se muda o valor de vetmenor[] que eu achei estão na função caminho(). Tenho quase toda certeza que a função verificar() não está influenciando nisso, pois está certa.

Os System.out.println que coloquei nos momentos que o vetmenor[] muda de valor são:

System.out.println(“Menor=”+menor);

System.out.println(“Entrou no menor!!@!”);

O código está lá em baixo, mas está mal organizado:

Vou tentar dar uma resumida nas coisas mais importantes:
conty é para mostrar quando é a primeira vez que o programa acha uma combinação válida.
conty=0 quer dizer que ainda o programa não achou nada válido.
conty=2 quer dizer que o programa achou pela primeira vez uma combinação válida.

vet2[] é para determinar quais caminhos diretos entre duas vilas é para o programa escolher para usar em suas combinações.
vet2[i]=0, significa que o caminho i, ou seja, o caminho vet[i][] não é para ser utilizado.
vet2[i]=1, significa que o caminho i, ou seja, o caminho vet[i][] é para ser utilizado.

vetmenor[] é o vetor que armazena o vet2[] que causa menos danos ambientais.

vet[][] representa todos os caminhos disponíveis para uso.

import java.util.Scanner;

public class Redotica {
static Scanner leitor=new Scanner(System.in);
static int n, m, permg, menor, vetmenor[],conty;

public static void main(String[] args) {
	// TODO Auto-generated method stub
	conty=0;
	test(1);	
	
}

public static void test(int num) {
	int n2,m2, vetmenor2[];
	n2=leitor.nextInt();
	m2=leitor.nextInt();
	m=m2;
	n=n2;
	
	if(n2!=0) {
		
		int vet2[]=new int[m2];
		int vet[][]=new int[m2][3];
		
		for(int i=0;i<m2;i++) {
			vet[i][0]=leitor.nextInt();
			vet[i][1]=leitor.nextInt();
			vet[i][2]=leitor.nextInt();
		}
		
		
		vetmenor2=new int[m2];
		conty=0;
		caminho(vet, 0, vet2);
		vetmenor2=vetmenor;
		
		//test(num+1);
		
		System.out.println("Teste "+num+ " Menor: "+menor);
		for(int i2=0;i2<m2;i2++) {
			if(vetmenor2[i2]==1) {
				System.out.print(vet[i2][0]+" "+vet[i2][1]);
				System.out.println("");
			}
		}
		
	}else {
		
	}
}

public static void caminho(int vet[][], int i, int vet2[]) {
	
	if(i<m) {
		vet2[i]=0;
		
		caminho(vet, i+1, vet2);
		
		vet2[i]=1;
		caminho(vet, i+1, vet2);
	}else {
		int cid;
		int vetcid[]=new int[n];
		int cont2=0;
		
		for(cid=2;cid<=n;cid++) {
			
			for(int i2=1;i2<n;i2++) {
				vetcid[i2]=0;
			}
			vetcid[0]=1;
			
			verificar(vet, vetcid, cid, 1, 0, vet2);
			
			if(permg==1) {
				cont2++;
			}
			
		}
		
		if(cont2==n-1) {
			
			System.out.println("Entro permg");
			int desastre=0;
			for(int i2=0;i2<m;i2++) {
				if(vet2[i2]==1) {
					desastre=desastre+vet[i2][2];
				}
			}
			System.out.println("Conty="+conty);
			if(conty==0) {
				
                                    //momento que vetmenor[] muda de valor
				menor=desastre;
				vetmenor=vet2;
				conty=2;
				System.out.println("Menor="+menor);
				for(int i2=0;i2<m;i2++) {
					if(vetmenor[i2]==1) {
						System.out.print(vet[i2][0]+" "+vet[i2][1]);
						System.out.println("");
					}
				}
			}else
			if(desastre<menor) {
                                    //momento que vetmenor[] muda de valor
				System.out.println("Entrou no menor!!@!");
				menor=desastre;
				vetmenor=vet2;
				
				
					System.out.println("Menor="+menor);
					for(int i2=0;i2<m;i2++) {
						if(vetmenor[i2]==1) {
							System.out.print(vet[i2][0]+" "+vet[i2][1]);
							System.out.println("");
						}
					}
				
				
			}
			
		}
		
	}
}

public static void verificar(int vet[][], int vetcid[],int cid, int cidatual,int cont, int vet2[]) {
	int i=0;
	permg=0;
	while((i<m)&&(permg==0)) {
		
		if((cidatual==vet[i][0])&&(vet2[i]==1)) {
			
			int i2=0;
			int perm=0;
			while((perm==0)&&(i2<n)) {
				if(vetcid[i2]==vet[i][1]) {
					perm=1;
				}
				i2++;
			}
			
			if(perm==0) {
				if(vet[i][1]==cid) {
					
					permg=1;
					
				}else {
					vetcid[cont]=vet[i][1];
					verificar(vet, vetcid, cid, vet[i][1], cont+1, vet2);
				}
			}
			
		}else if((cidatual==vet[i][1])&&(vet2[i]==1)){
			
			int i2=0;
			int perm=0;
			while((perm==0)&&(i2<n)) {
				if(vetcid[i2]==vet[i][0]) {
					perm=1;
				}
				i2++;
			}
			
			if(perm==0) {
				if(vet[i][0]==cid) {
					
					permg=1;
					
				}else {
					vetcid[cont]=vet[i][0];
					verificar(vet, vetcid, cid, vet[i][0], cont+1, vet2);
				}
			}
				
		}
		i++;
	}
	
}

}

Se vocês executarem o programa com os mesmos valores do teste que citei lá em cima, o programa vai retornar isso:

Entro permg
Conty=0
Menor=20
2 3
3 1
Entro permg
Conty=2
Entro permg
Conty=2
Entro permg
Conty=2
Teste 1 Menor: 20
1 2
2 3
3 1

O resultado final é as 4 ultimas linhas.
O estranho é que o valor do menor está certo, mas a combinação não e o programa em um dado momento achar a combinação que eu queria, mas logo muda. A questão é que eu não sei o como o vetmenor[] está mudando de valor sendo que os System.out.println que eu coloquei nos momentos em que o vetmenor[] muda de valor não estão sendo acionados, talvez eu tenha esquecido de algum outro lugar do código que o vetmenor[] mudar, mas acredito que não seja isso.
E a combinação vet2[ 1, 1, 1], que é a errada, é a ultima combinação a ser analisada pelo programa.