#include<stdio.h>
#include<stdlib.h>

int front = 0;
int rear = -1;

int max_cost = 9999;
int max_vartex = 0;
int max_edge = 0;

int start = 0;
int destination = 0;

int **graph;
int *cost;
int *stack;
int *visit_list;

void show_graph()
{
    for(int i=0; i<max_vartex; i++)
    {
        for(int j=0; j<max_vartex; j++)
            printf("%d ",graph[i][j]);
        printf("\n");
    }
}

void push(int v)
{
    stack[++rear] = v;
}

int pop()
{
    return stack[rear--];
}

bool goal(int v)
{
    if(v == destination) return true;
    else return false;
}

void sort_stack()
{
    int i, j;
    for(i=0; i<max_vartex-1; i++)
        for(j=i+1; j<max_vartex; j++)
            if(stack[i] > stack[j])
            {
                int temp = stack[i];
                stack[i] = stack[j];
                stack[j] = temp;
            }
}

bool dijkstra()
{
    if(rear < 0) return false;
    else
    {
        int temp_v = pop();
        visit_list[temp_v] = 1;

        if(goal(temp_v)) return true;
        else
        {
            for(int i=0; i<max_vartex; i++)
            {
                if(i != temp_v)
                {
                    if(graph[temp_v][i] != 0 && cost[i] > (cost[temp_v]+graph[temp_v][i]))
                    {
                        cost[i] = (cost[temp_v]+graph[temp_v][i]);
                        push(i);
                    }
                }
            }
        }
        sort_stack();
    }
    //dijkstra();
    //return
}

int main()
{
    printf("Enter Vertex : ");
    scanf("%d",&max_vartex);

    graph = (int **) malloc(max_vartex * sizeof (int *));
    for(int i=0; i<max_vartex; i++)
        graph[i] = (int *) malloc(max_vartex * sizeof (int));

    stack = (int *) malloc(max_vartex * sizeof (int));

    for(int i=0; i<max_vartex; i++)
    {
        stack[i] = 0;
        visit_list[i] = 0;
        cost[i] = max_cost;
        for(int j=0; j<max_vartex; j++)
            graph[i][j] = 0;
    }

    printf("Enter Edge : ");
    scanf("%d",&max_edge);

    printf("Enter Value as : Source Destination Cost\n");
    for(int i=0; i<max_edge; i++)
    {
        int s = 0;
        int d = 0;
        int c = 0;

        scanf("%d %d %d", &s, &d, &c);
        graph[s][d] = c;
        graph[d][s] = c;
    }

    printf("Enter Starting Vartex : ");
    scanf("%d",&start);
    cost[start] = 0;

    printf("Enter Destination Vartex : ");
    scanf("%d",&destination);

    push(start);
    dijkstra();

    show_graph();

    printf("Minimum Cost: %d",cost[destination]);

    return 0;
}