破烂默写本

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9){write(x/10);}
	putchar((x%10)+48);
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);

	return 0;
}

int f[N],n;
inline void init(){
	for(int i=1;i<=n;i++)f[i]=i;
	return;
}
int find(int d){
	if(f[d]!=d)f[d]=find(f[d]);
	return f[d];
}
inline void uni(int x,int y){
	f[find(x)]=find(y);
	return;
}
inline bool check(int x,int y){
	return (find(x)==find(y));
}

int h[N],to[M],nxt[M],tot=-1;
inline void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=h[u];
	h[u]=tot;
}//只建边，边之类的自己写
//只建单向边，无向边写两遍即可
//这个写法边的其实编号为0,判断是否遍历完写 ~i
//编号从1开始就写tot=0即可，判断是否遍历完写 i!=0
//编号从0还是需要先把整个h数组赋值为-1

void spfa(){
	while(!q.empty())q.pop();
	for(int i=1;i<=n;i++){dis[i]=inf;}
	dis[s]=0;inque[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inque[u]=0;
		for(int i=h[u];~i;i=nxt[i]){
			int v=to[i];
			if(dis[v]>dis[u]+w[i]){
				dis[v]=dis[u]+w[i];
				if(inque[v]==0){
					inque[v]=1;
					q.push(v);
				}
			}
		}
	}
}

int dis[N],inque[N],in[N];
queue<int>q;
bool spfa(){
	while(!q.empty())q.pop();
	for(int i=1;i<=n;i++){dis[i]=inf;in[i]=0;inque[i]=0;}
	dis[s]=0;inque[s]=1;in[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inque[u]=0;
		for(int i=h[u];~i;i=nxt[i]){
			int v=to[i];
			if(dis[v]>dis[u]+w[i]){
				dis[v]=dis[u]+w[i];
				if(inque[v]==0){
					inque[v]=1;
					q.push(v);
					++in[v];
					if(in[v]>n){
						return true;
					}
				}
			}
		}
	}
  return false;
}

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=1e5+7,M=2e5+7,inf=1e9+7;
int n,m,s;
int h[N],to[M],nxt[M],w[M],tot=-1;
inline void add(int u,int v,int z){
	to[++tot]=v;
	nxt[tot]=h[u];
	w[tot]=z;
	h[u]=tot;
}
int dis[N],vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
//小根堆
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	pair<int,int>tmp;
	dis[s]=0;
	tmp.first=dis[s];
	tmp.second=s;
	q.push(tmp);
	while(!q.empty()){
		tmp=q.top();
		q.pop();
		int d=tmp.first;
		int u=tmp.second;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=h[u];~i;i=nxt[i]){
			int v=to[i];
			if(dis[v]>d+w[i]){		
				dis[v]=d+w[i];
				if(!vis[v]){
					pair<int,int>tmmp;
					tmmp.first=dis[v];
					tmmp.second=v;
					q.push(tmmp);
				}
			}
		}
	}
}
int main(){
	n=read();m=read();s=read();
	for(int i=1;i<=n;i++)h[i]=-1;// pay attention to it
	for(int i=1;i<=m;i++){
		int u,v,z;
		u=read();v=read();z=read();
		add(u,v,z);
	}
	dij();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
    return 0;
}

void dfs(int x,int f){
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=1;i<=18;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		if(fa[x][i]==0)break;
	}
	for(int i=h[x];~i;i=nxt[i]){
		if(to[i]!=f){
			dfs(to[i],x);
		}
	}
	return;
}
int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int i=18;i>=0;i--){
		if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
	}
	if(a==b)return a;
	for(int i=18;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[a][0];
}
//数字18的地方根据题目自行修改

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9){write(x/10);}
	putchar((x%10)+48);
}
const int N=2e5+7;
struct edge{
	int u,v,w;
}e[N];
bool cmp(edge x,edge y){
	if(x.w<y.w)return true;
	else return false;
}
int n,m,f[N],tot,ans;
int find(int x){
	if(x!=f[x])f[x]=find(f[x]);
	return f[x];
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		e[i].u=read();
		e[i].v=read();
		e[i].w=read();
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int u=e[i].u;
		int v=e[i].v;
		int w=e[i].w;
		if(find(u)!=find(v)){
			ans+=w;
			f[find(u)]=find(v);
			++tot;
		}
	}
	if(tot==n-1)write(ans);
	else cout<<"orz";
	return 0;
}