#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#include<cstdio>
#define lmax 50050
#define INFINIT 0x3f3f3f3f
using namespace std;
struct nod
{
    int inf;
    nod *urm;
};
vector<pair <int,int> > L[lmax];
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
int D[lmax],n,m,inc=1;
long contor;
bool viz[lmax];
void init_D(int inc)
{
    int i;
    for(i=1; i<=n; i++)
        if(i!=inc)
            D[i]=INFINIT;
}
void read()
{
    int i,x;
    pair<int,int> y,yy;
    fscanf(f,"%d %d",&n,&m);
    for(i=1; i<=m; i++)
        fscanf(f,"%d %d %d",&x,&y.first,&y.second),L[x].push_back(y);
}
int extract_min()
{
    int i,minim=INFINIT,best=0;
    for(i=1; i<=n; i++)
        if(D[i]<minim && !viz[i])
            minim=D[i],best=i;
    viz[best]=1;
    return best;
}
bool viz_check()
{
    int i;
    for(i=1; i<=n; i++)
        if(!viz[i])
            return 1;
    return 0;
}
bool update_dist(int x)
{
    unsigned int i;
    bool test=0;
    for(i=0; i<L[x].size(); i++)
        if(D[x]+L[x][i].second<D[L[x][i].first])
            D[L[x][i].first]=D[x]+L[x][i].second,test=1;
    return 1;
}
void Djikstra()
{
    int muchie=1;
    init_D(inc);
    while(muchie)
    {
        muchie=extract_min();
        contor++;
        if(!update_dist(muchie))
            muchie=0;
    }
}
void show_sol()
{
    unsigned int i;
    for(i=2; i<=n; i++)
        if(D[i]<INFINIT)
            fprintf(g,"%d ",D[i]);
        else
            fprintf(g,"0 ");
}
int main()
{
    read();
    Djikstra();
    cout<<contor<<"\n";
    show_sol();
    fclose(f);
    fclose(g);
    return 0;
}