#include <iostream>
#include <fstream>
#include <cmath>
     
using namespace std;
     
int miasto[401],miastoX[401],miastoY[401],wybrane[401];
int odwiedzone[401];
int tab[401];
int iloscM,maxx,najtrasa;
int najlepszy;
     
int droga( int suma,long int profit,int poprz,int ilosc)
{
    int i,j;
    int odleglosc,powrot;
        
       
    for(i=2;i<=iloscM;i++)
    {    
        odleglosc=rintf(sqrt((miastoX[i]-miastoX[poprz])*(miastoX[i]-miastoX[poprz])+(miastoY[i]-miastoY[poprz])*(miastoY[i]-miastoY[poprz])));
        powrot=rintf(sqrt(((miastoX[1]-miastoX[i])*(miastoX[1]-miastoX[i])+(miastoY[1]-miastoY[i])*(miastoY[1]-miastoY[i]))));
                     
        if(odleglosc+suma+powrot<=maxx && odwiedzone[i]==0 && miasto[i]!=0){
            suma=suma+odleglosc;
            profit=profit+miasto[i];      
            odwiedzone[i]=1;
            ilosc++;
            tab[ilosc]=i;
            
			if(najlepszy<=profit){
                
				if(najlepszy==profit&&suma+powrot<najtrasa)
                {                 
	            	for(j=1;j<=iloscM;j++){
	                    wybrane[j]=tab[j];
	                }
	                najlepszy=profit;
	                najtrasa=suma+powrot;
                }
                    
	    		if(najlepszy!=profit){ 	
	                for(j=1;j<=iloscM;j++){
		                wybrane[j]=tab[j];
		            }
		            najlepszy=profit;
		            najtrasa=suma+powrot;
	            }
            }
                
            droga(suma,profit,i,ilosc);
            tab[ilosc]=0;
            ilosc--;             
            odwiedzone[i]=0;     
            suma=suma-odleglosc;
            profit=profit-miasto[i];
     
        }
    }
}
     
int main()
{
    FILE *fp;
    int i;
       
    ifstream plikin;
    plikin.open("in1.txt");
    plikin>>iloscM>>maxx;
           
    for(i=1;i<=iloscM;i++)
    {
        plikin>>miastoX[i]>>miastoY[i]>>miasto[i];
		tab[i]=0;
        odwiedzone[i]=0;
        wybrane[i]=0;
    }
       
    int odwiedzone[iloscM],tab[iloscM];
    
    wybrane[0]=1;
    odwiedzone[1]=1;
     
    droga(0,0,1,1);
    printf("Najlepszy profit: %d\n",najlepszy);
    for(i=0;i<=iloscM;i++)
    {
        if(wybrane[i]!=0)
        {
        	printf("%d ",wybrane[i]);
        } 
    }
    printf(" 1 \nDlugosc trasy: %d", najtrasa);
       // system("PAUSE");
	return 0;
}