




import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings("""ignore""")

__SCREAMING_SNAKE_CASE    :   Optional[Any]       ="""K-MEANS-CLUST/ """





def 			lowerCAmelCase_			(  lowerCamelCase:       List[str]     ,				lowerCamelCase:       int     ,				lowerCamelCase:       int=None						)					->			int:


      '''simple docstring'''




      if seed is not None:  # useful for obtaining consistent results
            np.random.seed(lowerCamelCase						)
      lowerCamelCase__        =				data.shape[0]  # number of data points

      # Pick K indices from range [0, N).
      lowerCamelCase__        =				np.random.randint(0     ,				lowerCamelCase     ,				lowerCamelCase						)

      # Keep centroids as dense format, as many entries will be nonzero due to averaging.
      # As long as at least one document in a cluster contains a word,
      # it will carry a nonzero weight in the TF-IDF vector of the centroid.
      lowerCamelCase__        =				data[rand_indices, :]

      return centroids





def 			lowerCAmelCase_			(  lowerCamelCase:       Optional[Any]     ,				lowerCamelCase:       Dict						)					->			Any:


      '''simple docstring'''




      return pairwise_distances(lowerCamelCase     ,				lowerCamelCase     ,				metric='euclidean'						)





def 			lowerCAmelCase_			(  lowerCamelCase:       Union[str, Any]     ,				lowerCamelCase:       Optional[int]						)					->			Dict:


      '''simple docstring'''




      lowerCamelCase__        =				centroid_pairwise_dist(lowerCamelCase     ,				lowerCamelCase						)

      # Compute cluster assignments for each data point:
      # Fill in the blank (RHS only)
      lowerCamelCase__        =				np.argmin(lowerCamelCase     ,				axis=1						)

      return cluster_assignment





def 			lowerCAmelCase_			(  lowerCamelCase:       Optional[Any]     ,				lowerCamelCase:       Optional[int]     ,				lowerCamelCase:       Any						)					->			Any:


      '''simple docstring'''




      lowerCamelCase__        =				[]
      for i in range(lowerCamelCase						):
            # Select all data points that belong to cluster i. Fill in the blank (RHS only)
            lowerCamelCase__        =				data[cluster_assignment == i]
            # Compute the mean of the data points. Fill in the blank (RHS only)
            lowerCamelCase__        =				member_data_points.mean(axis=0						)
            new_centroids.append(lowerCamelCase						)
      lowerCamelCase__        =				np.array(lowerCamelCase						)

      return new_centroids





def 			lowerCAmelCase_			(  lowerCamelCase:       Optional[Any]     ,				lowerCamelCase:       Tuple     ,				lowerCamelCase:       str     ,				lowerCamelCase:       Optional[Any]						)					->			Any:


      '''simple docstring'''




      lowerCamelCase__        =				0.0
      for i in range(lowerCamelCase						):
            # Select all data points that belong to cluster i. Fill in the blank (RHS only)
            lowerCamelCase__        =				data[cluster_assignment == i, :]

            if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
                  # Compute distances from centroid to data points (RHS only)
                  lowerCamelCase__        =				pairwise_distances(
                      lowerCamelCase     ,				[centroids[i]]     ,				metric='euclidean'						)
                  lowerCamelCase__        =				distances**2
                  heterogeneity += np.sum(lowerCamelCase						)

      return heterogeneity





def 			lowerCAmelCase_			(  lowerCamelCase:       List[str]     ,				lowerCamelCase:       Any						)					->			Union[str, Any]:


      '''simple docstring'''




      plt.figure(figsize=(7, 4)						)
      plt.plot(lowerCamelCase     ,				linewidth=4						)
      plt.xlabel('# Iterations'						)
      plt.ylabel('Heterogeneity'						)
      plt.title(f"""Heterogeneity of clustering over time, K={k:d}"""						)
      plt.rcParams.update({'font.size': 16}						)
      plt.show()





def 			lowerCAmelCase_			(  lowerCamelCase:       Dict     ,				lowerCamelCase:       Optional[int]     ,				lowerCamelCase:       List[str]     ,				lowerCamelCase:       Tuple=5_00     ,				lowerCamelCase:       List[Any]=None     ,				lowerCamelCase:       int=False						)					->			str:


      '''simple docstring'''




      lowerCamelCase__        =				initial_centroids[:]
      lowerCamelCase__        =				None

      for itr in range(lowerCamelCase						):
            if verbose:
                  print(lowerCamelCase     ,				end=''						)

            # 1. Make cluster assignments using nearest centroids
            lowerCamelCase__        =				assign_clusters(lowerCamelCase     ,				lowerCamelCase						)

            # 2. Compute a new centroid for each of the k clusters, averaging all data
            #    points assigned to that cluster.
            lowerCamelCase__        =				revise_centroids(lowerCamelCase     ,				lowerCamelCase     ,				lowerCamelCase						)

            # Check for convergence: if none of the assignments changed, stop
            if (
                prev_cluster_assignment is not None
                and (prev_cluster_assignment == cluster_assignment).all()
            ):
                  break

            # Print number of new assignments
            if prev_cluster_assignment is not None:
                  lowerCamelCase__        =				np.sum(prev_cluster_assignment != cluster_assignment						)
                  if verbose:
                        print(
                            f"""    {num_changed:5d} elements changed their cluster assignment."""						)

        # Record heterogeneity convergence metric
            if record_heterogeneity is not None:
                  # YOUR CODE HERE
                  lowerCamelCase__        =				compute_heterogeneity(lowerCamelCase     ,				lowerCamelCase     ,				lowerCamelCase     ,				lowerCamelCase						)
                  record_heterogeneity.append(lowerCamelCase						)

            lowerCamelCase__        =				cluster_assignment[:]

      return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
      from sklearn import datasets as ds

      __SCREAMING_SNAKE_CASE    :   List[str]       =ds.load_iris()
      __SCREAMING_SNAKE_CASE    :   Union[str, Any]       =3
      __SCREAMING_SNAKE_CASE    :   Union[str, Any]       =[]
      __SCREAMING_SNAKE_CASE    :   Optional[int]       =get_initial_centroids(dataset["""data"""], k, seed=0)
      __SCREAMING_SNAKE_CASE    :   Dict       =kmeans(
          dataset["""data"""],
          k,
          initial_centroids,
          maxiter=400,
          record_heterogeneity=heterogeneity,
          verbose=True,
      )
      plot_heterogeneity(heterogeneity, k)





def 			lowerCAmelCase_			(  lowerCamelCase:       pd.DataFrame     ,				lowerCamelCase:       np.ndarray     ,				lowerCamelCase:       int=None						)					->			pd.DataFrame:


      '''simple docstring'''




      if fill_missing_report:
            lowerCamelCase__        =				df.fillna(value=lowerCamelCase						)
      lowerCamelCase__        =				1
      lowerCamelCase__        =				df.select_dtypes(np.number						).columns
      lowerCamelCase__        =				(
          df.groupby(['Cluster']						)[  # construct report dataframe
              numeric_cols
          ]  # group by cluster number
          .agg(
              [
                  ('sum', np.sum),
                  ('mean_with_zeros', lambda lowerCamelCase						: np.mean(np.nan_to_num(lowerCamelCase						)						)),
                  ('mean_without_zeros', lambda lowerCamelCase						: x.replace(0     ,				np.NaN						).mean()),
                  (
                      'mean_25-75',
                      lambda lowerCamelCase						: np.mean(
                          np.nan_to_num(
                              sorted(lowerCamelCase						)[
                                  round(len(lowerCamelCase						) * 25 / 1_00						) : round(len(lowerCamelCase						) * 75 / 1_00						)
                              ]						)						),
                  ),
                  ('mean_with_na', np.mean),
                  ('min', lambda lowerCamelCase						: x.min()),
                  ('5%', lambda lowerCamelCase						: x.quantile(0.05						)),
                  ('25%', lambda lowerCamelCase						: x.quantile(0.25						)),
                  ('50%', lambda lowerCamelCase						: x.quantile(0.50						)),
                  ('75%', lambda lowerCamelCase						: x.quantile(0.75						)),
                  ('95%', lambda lowerCamelCase						: x.quantile(0.95						)),
                  ('max', lambda lowerCamelCase						: x.max()),
                  ('count', lambda lowerCamelCase						: x.count()),
                  ('stdev', lambda lowerCamelCase						: x.std()),
                  ('mode', lambda lowerCamelCase						: x.mode()[0]),
                  ('median', lambda lowerCamelCase						: x.median()),
                  ('# > 0', lambda lowerCamelCase						: (x > 0).sum()),
              ]						)
          .T.reset_index()
          .rename(index=lowerCamelCase     ,				columns={'level_0': 'Features', 'level_1': 'Type'}						)
      )  # rename columns
      # calculate the size of cluster(count of clientID's)
      lowerCamelCase__        =				report[
          (report['Features'] == 'dummy') & (report['Type'] == 'count')
      ].copy()  # avoid SettingWithCopyWarning
      lowerCamelCase__        =				(
          'ClusterSize'  # rename created cluster df to match report column names
      )
      lowerCamelCase__        =				'# of Customers'
      lowerCamelCase__        =				pd.DataFrame(
          clustersize.iloc[:, 2:].values
          / clustersize.iloc[:, 2:].values.sum()						)
      lowerCamelCase__        =				'% of Customers'  # rename created cluster df to match report column names
      lowerCamelCase__        =				'ClusterProportion'
      lowerCamelCase__        =				clusterproportion.columns.tolist()
      lowerCamelCase__        =				cols[-2:] + cols[:-2]
      lowerCamelCase__        =				clusterproportion[cols]  # rearrange columns to match report
      lowerCamelCase__        =				report.columns
      lowerCamelCase__        =				pd.DataFrame(
          abs(
              report[report['Type'] == 'count'].iloc[:, 2:].values
              - clustersize.iloc[:, 2:].values						)						)  # generating df with count of nan values
      lowerCamelCase__        =				0
      lowerCamelCase__        =				'# of nan'
      lowerCamelCase__        =				report[
          report['Type'] == 'count'
      ].Features.tolist()  # filling values in order to match report
      lowerCamelCase__        =				a.columns.tolist()
      lowerCamelCase__        =				cols[-2:] + cols[:-2]
      lowerCamelCase__        =				a[cols]  # rearrange columns to match report
      lowerCamelCase__        =				report.columns  # rename columns to match report
      lowerCamelCase__        =				report.drop(
          report[report.Type == 'count'].index						)  # drop count values except cluster size
      lowerCamelCase__        =				pd.concat(
          [report, a, clustersize, clusterproportion]     ,				axis=0						)  # concat report with clustert size and nan values
      lowerCamelCase__        =				report['Features'].isin(lowerCamelCase						)
      lowerCamelCase__        =				report.columns.tolist()
      lowerCamelCase__        =				cols[0:2] + cols[-1:] + cols[2:-1]
      lowerCamelCase__        =				report[cols]
      lowerCamelCase__        =				{
          'ClusterSize': 9,
          'ClusterProportion': 8,
          'mean_with_zeros': 7,
          'mean_with_na': 6,
          'max': 5,
          '50%': 4,
          'min': 3,
          '25%': 2,
          '75%': 1,
          '# of nan': 0,
          '# > 0': -1,
          'sum_with_na': -2,
      }
      lowerCamelCase__        =				(
          report.assign(
              Sortera=lambda lowerCamelCase						: x.Type.map(lowerCamelCase						)     ,				Sortera=lambda lowerCamelCase						: list(reversed(range(len(lowerCamelCase						)						)						)						)     ,				)
          .sort_values(['Sorter1', 'Mark', 'Sorter2']     ,				ascending=lowerCamelCase						)
          .drop(['Sorter1', 'Sorter2']     ,				axis=1						)
      )
      lowerCamelCase__        =				''
      lowerCamelCase__        =				report.reset_index()
      lowerCamelCase__        =				report.drop(columns=['index']						)
      return report


if __name__ == "__main__":
      import doctest

      doctest.testmod()





def 			lowerCAmelCase_			(  lowerCamelCase:       int     ,				lowerCamelCase:       list[tuple[int, int, int]]						)					->			list[tuple[int, int, int]]:


      '''simple docstring'''




      lowerCamelCase__        =				sorted(lowerCamelCase     ,				key=lambda lowerCamelCase						: edge[2]						)

      lowerCamelCase__        =				list(range(lowerCamelCase						)						)

      def find_parent(lowerCamelCase:       int						):
            if i != parent[i]:
                  lowerCamelCase__        =				find_parent(parent[i]						)
            return parent[i]

      lowerCamelCase__        =				0
      lowerCamelCase__        =				[]

      for edge in edges:
            lowerCamelCase__        =				find_parent(edge[0]						)
            lowerCamelCase__        =				find_parent(edge[1]						)
            if parent_a != parent_b:
                  minimum_spanning_tree_cost += edge[2]
                  minimum_spanning_tree.append(lowerCamelCase						)
                  lowerCamelCase__        =				parent_b

      return minimum_spanning_tree


if __name__ == "__main__":  # pragma: no cover
      __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    :   Tuple       =list(map(int, input().strip().split()))
      __SCREAMING_SNAKE_CASE    :   Optional[Any]       =[]

      for _ in range(num_edges):
            __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    :   Optional[int]       =(int(x) for x in input().strip().split())
            edges.append((nodea, nodea, cost))

      kruskal(num_nodes, edges)