#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long int lli;
int visited[10010];
lli dist[10010];
#define pp pair<int,int>
// comparator for min heap
class Prioritize
{
public:
int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
{
return p1.second > p2.second;
}
};
int main()
{
int t;
cin>>t;
while(t--)
{
list<pair<lli,lli> >li[10010];
lli n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
lli a,b,c;
cin>>a>>b>>c;
li[a].push_back(make_pair(b,c));
li[b].push_back(make_pair(a,c));
}
for(int i=1;i<=n;i++)
{
visited[i]=0;
dist[i]=INT_MAX;
}
// declaring pq;
priority_queue<pp, vector<pp > , Prioritize > q;
dist[1]=0;
lli ans=0;
int f=0;
// need to find distance of all node from 1
lli start=1;
q.push(make_pair(1,0));
while(!q.empty())
{
list<pair<lli,lli> > :: iterator it;
lli start=q.top().first;
q.pop();
if(visited[start]==1) continue;
visited[start]=1;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(!visited[it->first] && dist[it->first]>dist[start]+it->second)
{
q.push(make_pair(it->first,dist[start]+it->second));
dist[it->first]=dist[start]+it->second;
}
}
}
for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
}
return 0;
}
No comments:
Post a Comment