#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
vector <strut> h; //heap
int broasca[nr];

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

    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.push_back(q);
            int in=i;
            while (h[in].b<h[in/2].b && in>1)
            {
                swap(h[in],h[in/2]);
                in=in/2;
            }
        }
    }

    m=n;
    n=h.size();
    while (n!=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.push_back(aux);
                int in=h.size()-1;
                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<h.size();++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 (h.size()>2){
            h[1]=h[h.size()-1]; // decapitare+echilibrare heap
                j=1;
            h.pop_back();
            n=h.size()-1;
            if (j*2+1<=n)
                while (j*2+1<=n)
                {
                    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==n) break;
                }
            else if (j*2==n && h[j].b>h[j*2].b)
            
                swap (h[j],h[j*2]);
                
            }
        else break;
    }
 
    for (i=2;i<=m;++i)
        if (broasca[i]==-1) g<<0<<' '; else
            g<<broasca[i]<<' ';
    f.close();
    g.close();
    
    return 0;
}