code is as:
#include<bits/stdc++.h>
using namespace std;
int find(long long * d,bool * v,int n)
{
int mv=INT_MAX,mi=-1;
for(int i=1;i<=n;i++)
{
if(d[i]<mv&&!v[i])
{
mv=d[i];
mi=i;
}
}
return mi;
}
void res(vector<vector < long long > > graph,int n,int s)
{
long long dist[n+1];
bool vis[n+1];
for(int i=0;i<=n;i++)
{
dist[i]=INT_MAX;
vis[i]=0;
}
dist[s]=0;
int k=s;
while(k!=-1)
{
// cout<<k<<endl;
vis[k]=1;
for(int i=1;i<=n;i++)
{
if(graph[k][i]!=INT_MAX&&!vis[i]&&dist[k]!=INT_MAX)
{
dist[i]=min(dist[i],dist[k]+graph[k][i]);
}
}
k=find(dist,vis,n);
}
for(int i=1;i<=n;i++)
{if(i!=s)
{
if(dist[i]==INT_MAX)
cout<<"-1 “;
else
cout<<dist[i]<<” ";
}
}
cout<<endl;
}
int main() {
int t,n,m;
cin>>t;
while(t–)
{
cin>>n>>m;
vector< vector< long long > > graph;
// cout<<graph.size();
vector k;
for(int i=0;i<=n;i++)
{
k.push_back(INT_MAX);
}
// cout<<" “<<k.size();
for(int i=0;i<=n;i++)
{
graph.push_back(k);
// cout<<graph.size()<<” “<<graph[0].size()<<endl;
}
//cout<<graph.size()<<” "<<graph[0].size()<<endl;
for(int i=0;i<m;i++)
{
int x,y,r;
cin>>x>>y>>r;
graph[x][y]=r;
graph[y][x]=r;
}
int s;
cin>>s;
res(graph,n,s);
}
return 0;
}