#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
int m,n,k,a[2002][2002],cost[2002],viz[2002];
int prim()
{

    int j,l,k=1,i,jmin,minim=9999;
    cost[1]=0;
    i=1;
    viz[1]=1;
    for(k=1;k<=n;k++)
    {
        minim=9999;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(a[i][j]!=0&&viz[j]==0&&viz[i]==1&&a[i][j]+cost[i]<minim)
                {
                    minim=a[i][j]+cost[i];
                    jmin=j;
                }
                for(i=1;i<=n;i++)
                    cout<<viz[i]<<" ";
                cout<<endl;
        viz[jmin]=1;
        cost[jmin]=minim;
        if(jmin == n)
            return cost[jmin];
    }
}
int main()
{
    int x,y,z,i;
    fin>>n>>m;
    fin>>k;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        a[x][y]=z;
        a[y][x]=z;
    }
    for(i=2;i<=n;i++)
        cost[i]=9999;

    fout<<prim();
    fin.close();
    fout.close();
    return 0;
}