思路：
判断一个点在不在最短路上好办，就是从这个点到1的最短距离加上到n的最短距离加起来
判断是不是在所有最短路上，则把所有最短路边加上建一个新图，如果新图上这个点是割点，那明显所有最短路都经过了这个点
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>using namespace std;typedef long long ll;const int maxn = 2e5 + 7;
const int MX = 1005;
const ll INF = 1e18;
int head[MX],nex[maxn * 2],to[maxn * 2],val[maxn * 2],tot;;
int Head[MX],Nex[maxn * 2],To[maxn * 2],Val[maxn * 2],Tot;
ll dis1[MX],dis2[MX];
int vis[MX],ans[MX],dfn[MX],low[MX],dfs_clock,root;
bool cut[MX];
int n,m;void add(int x,int y,int z) {to[++tot] = y;nex[tot] = head[x];val[tot] = z;head[x] = tot;
}void Add(int x,int y,int z) {To[++Tot] = y;Nex[Tot] = Head[x];Val[Tot] = z;Head[x] = Tot;
}void init() {memset(head,0,sizeof(head));memset(Head,0,sizeof(Head));tot = Tot = 0;memset(ans,0,sizeof(ans));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(cut,false,sizeof(cut));dfs_clock = 0;}void dijkstra(int sta,ll *dis) {for(int i = 1;i <= n;i++) {dis[i] = INF;vis[i] = 0;}priority_queue<pair<int,int> >Q;dis[sta] = 0;Q.push({0,sta});while(!Q.empty()) {pair<int,int>now = Q.top();Q.pop();int u = now.second;vis[u] = 1;for(int i = head[u];i;i = nex[i]) {int v = to[i],w = val[i];if(vis[v]) continue;if(dis[v] > dis[u] + w) {dis[v] = dis[u] + w;Q.push({-dis[v],v});}}}
}void tarjan(int x) {dfn[x] = low[x] = ++dfs_clock;int flag = 0;for(int i = Head[x];i;i = Nex[i]) {int y = To[i];if(!dfn[y]) {tarjan(y);low[x] = min(low[x],low[y]);if(low[y] >= dfn[x]) {flag++;if(x != root || flag > 1) cut[x] = true;}}else {low[x] = min(low[x],dfn[y]);}}
}int main() {int T;scanf("%d",&T);while(T--) {init();scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dijkstra(1,dis1);dijkstra(n,dis2);ll min_dis = dis1[n];for(int i = 1;i <= n;i++) {if(dis1[i] + dis2[i] == min_dis) {ans[i] = 2;}else ans[i] = 0;for(int j = head[i];j;j = nex[j]) {int v = to[j],w = val[j];if(dis1[i] + w + dis2[v] == min_dis) {Add(i,v,w);Add(v,i,w);}}}for(int i = 1;i <= n;i++) {if(!dfn[i]) root = i,tarjan(i);}for(int i = 1;i <= n;i++) {if((cut[i] && ans[i] == 2) || i == 1 || i == n) ans[i] = 1;printf("%d ",ans[i]);}printf("\n");}return 0;
}