Dijkstra模板
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(long long x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const long long maxn=2e5+5;
long long dis[maxn],head[maxn],eid=1,n,m,u,v,w,vis[maxn];
struct node
{
long long v,next,w;
}e[maxn];
inline void insert(long long u,long long v,long long w)
{
e[eid].v=v;
e[eid].next=head[u];
e[eid].w=w;
head[u]=eid++;
}
inline void Dijkstra(long long s)
{
for(int i=1;i<=200000;i++)
{
dis[i]=0x7fffffff;
}
dis[s]=0;
priority_queue<long long,vector<int>,greater<int> > Q;
while(!Q.empty())Q.pop();
Q.push(s);
while(!Q.empty())
{
long long u=Q.top();
Q.pop();
if(!vis[u])
{
vis[u]=1;
for(long long i=head[u];i;i=e[i].next)
{
long long v=e[i].v;
dis[v]=min(dis[v],dis[u]+e[i].w);
Q.push(v);
}
}
}
return;
}
int main()
{
n=read();
m=read();
for(long long i=1;i<=m;i++)
{
u=read();
v=read();
w=read();
insert(u,v,w);
insert(v,u,w);
}
Dijkstra(1);
for(long long i=1;i<=n;i++)
{
write(dis[i]);
putchar(' ');
}
}