#include <fstream>
#include <vector>
#define nr 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct strut
{
    int a,b;
};

vector <strut > vec[nr]; // lista cu noduri
strut h[nr]; //heap
int broasca[nr];

int main()
{int n,m,i,j,y,x,z; int k=0;
    strut aux;
 
  
    f>>n>>m;
    for (i=1;i<=n;++i) broasca[i]=-1;


    for (i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        strut q;
        q.a=y;
        q.b=z;
        vec[x].push_back(q);
        if (x==1)
        {
            broasca[y]=z;
            
            h[++k]=q;
            int in=i;
            while (h[in].b<h[in/2].b && in>1)
            {
                swap(h[in],h[in/2]);
                in=in/2;
            }
        }
    }
    while (k!=0)
    {
        for (i=1;i<=k;++i) g<<h[i].a<<' ';
        g<<"\n";
        x=h[1].a; // heapuire
        i=0;
        while (vec[x].size()!=i)
        {
            if (broasca[vec[x][i].a]==-1)
            {
                broasca[vec[x][i].a]=vec[x][i].b+broasca[x];
                aux.a=vec[x][i].a;
                aux.b=broasca[vec[x][i].a];
                h[++k]=aux;
                int in=k;
                while (h[in].b<h[in/2].b && in>3)
                {
                    swap(h[in],h[in/2]);
                    in=in/2;
                }
                
            }
            else if (broasca[vec[x][i].a]>vec[x][i].b+broasca[x])
            {
                int in;
                for (in=1;in<=k;++in)
                    if (h[in].b==broasca[vec[x][i].a]) break;
                h[in].b=vec[x][i].b+broasca[x];
                broasca[vec[x][i].a]=vec[x][i].b+broasca[x];
                while (h[in].b<h[in/2].b && in>3)
                {
                    swap(h[in],h[in/2]);
                    in=in/2;
                }

            }
            ++i;
        }
        
        
        if (k>1){
            h[1]=h[k]; // decapitare+echilibrare heap
                j=1;
            k--;
            if (j*2+1<=k)
                while (j*2+1<=k)
                {
                    if (h[j].b>h[j*2].b && h[j*2].b<=h[j*2+1].b)
                    {
                        swap(h[j],h[j*2]);
                        j=j*2;
                        
                    }
                    else if ((h[j].b > h[j*2+1].b) && (h[j*2+1].b <= h[j*2].b))
                    {
                        swap(h[j],h[j*2+1]);
                      
                        j=j*2+1;
                    }
                    else break;
                    if (j==k) break;
                }
            else if (j*2==k && h[j].b>h[j*2].b)
            
                swap (h[j],h[j*2]);
                
            }
        else break;
        
    }
 
    for (i=2;i<=n;++i)
        if (broasca[i]==-1) g<<0<<' '; else
            g<<broasca[i]<<' ';
    f.close();
    g.close();
    
    return 0;
}