#include <fstream>
#include <vector>

#define nr 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct strut
{
    long long a,b;
};

vector <strut > vec[nr]; // lista cu noduri
strut h[nr]; //heap
long long broasca[nr];
long long n,m,i,j,y,x,z; int k=0;
strut aux;


int main()
{
    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=k;
            while (h[in].b<h[in/2].b && in>1)
            {
                swap(h[in],h[in/2]);
                
                in=in/2;
            }
        }
    }
    
    
    while (k!=0)
    {
        
        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;
        }
        
        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]);
        
        
        
    }
    
    for (i=2;i<=n;++i)
        if (broasca[i]==-1) g<<0<<' '; else
            g<<broasca[i]<<' ';
    f.close();
    g.close();
    
    return 0;
}