void Dijkstra(Cidade **lista,int qtdCidade, int qtdMoeda)
{
    int **Distancias,**Marcados,tamanho=1,j,k,verticeAtual,moedaAtual,CustoTotal=0;
    Heap *heap;
    Cidade *TEMP;

    Distancias = matriz_create (qtdCidade+1,qtdMoeda+1);
    Marcados = matriz_create (qtdCidade+1,qtdMoeda+1);
    heap = (Heap*)calloc(15000,sizeof(Heap));

    for(j=1;j<=qtdCidade;j++)
    {
        for(k=1;k<=qtdMoeda;k++)
        {
            Distancias[j][k] = 0x3f3f3f3f;
        }
    }

    Distancias[1][qtdMoeda] = 0;

    heap[1].vertice = 1;
    heap[1].distancia = 0;
    heap[1].pedagio = qtdMoeda;
    Marcados[1][qtdMoeda] = 1;

    while(tamanho >= 1)
    {
         ControiHeap(heap,tamanho);
         verticeAtual = heap[1].vertice;
         moedaAtual = heap[1].pedagio;
         ///remoção no heap
         heap[1] = heap[tamanho];
         tamanho--;
         heapify(heap,tamanho,1);

         Marcados[verticeAtual][moedaAtual] = 1;

         TEMP = lista[verticeAtual];
         while(TEMP->NEXT != NULL)
         {
             TEMP = TEMP->NEXT;
             if((TEMP->pedagio + Distancias[verticeAtual][moedaAtual]) < Distancias[TEMP->cidade][TEMP->pedagio] && Marcados[TEMP->cidade][TEMP->pedagio] == 0 )
             {
                 Distancias[TEMP->cidade][TEMP->pedagio] = TEMP->pedagio + Distancias[verticeAtual][moedaAtual];
                 tamanho++;
                 heap[tamanho].vertice = TEMP->cidade;
                 heap[tamanho].distancia = TEMP->comprimento;
                 heap[tamanho].pedagio = TEMP->pedagio;
                 ControiHeap(heap,tamanho);
             }
         }
    }

    Quicksort(Distancias[qtdCidade],1,qtdMoeda);
    if(Distancias[qtdCidade][1] != 0x3f3f3f3f )
    {
        fprintf(Saida,"%d\n",Distancias[qtdCidade][1]);
    }
    else
    {
        fprintf(Saida,"-1\n");
    }
    liberarMatriz (Marcados,qtdCidade);
    liberarMatriz (Distancias,qtdCidade);
}