Dijkstra

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int n;
int a[1000][1000];

//function to calculate the shortest distance
int shortestDistance(int distance[], bool splset[]){
    int min=INT_MAX, min_idx;
    for(int v=0; v<n; v++){
        if(splset[v]==false && distance[v]<=min)
            min=distance[v], min_idx=v;
    }
    return min_idx;
}

void print_solution(int distance[]){
    for(int i=0; i<n; i++)
        cout<<i<<" " <<distance[i]<<endl;
}

void djkastra(int src){
    int distance[1000];
    bool splset[1000];

    for(int i=0; i<n; i++)
        distance[i]=INT_MAX, splset[i]=false;

    distance[src]=0;
    for(int i=0; i<n-1; i++){
        int u=shortestDistance(distance,splset);
        splset[u]=true;

        for(int v=0; v<n; v++){
            if(!splset[v] && a[u][v] && distance[u]!=INT_MAX && distance[u] + a[u][v] < distance[v])
                distance[v] = distance[u] + a[u][v];
        }
    }
    print_solution(distance);
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>a[i][j];

        djkastra(0);
    }
}