#include <fstream>
#include <vector>
#define N 50002
#define INF 2000000000

using namespace std;

struct bla
{
    int ve,co;
};
vector <bla> graph[N];
int dist[N],heap[N],cate,poz[N];


void up(int nod, int i)
{
    while(i>1 && dist[heap[i/2]]>dist[heap[i]])
    {
        swap(poz[heap[i/2]],poz[heap[i]]);
        swap(heap[i],heap[i/2]);
        i/=2;
    }
}
void down(int nod, int i)
{
    int pozfiu;
    do
    {
        pozfiu=0;
        if(2*i<=cate)
        {
            pozfiu=2*i;
            if(2*i+1<=cate && dist[heap[2*i+1]]<dist[heap[2*i]])
                pozfiu=2*i+1;
        }
        if(pozfiu && dist[heap[pozfiu]]<dist[nod])
        {
            swap(poz[heap[pozfiu]],poz[nod]);
            swap(heap[pozfiu],heap[i]);
            i=pozfiu;
        }
        else
            pozfiu=0;
    }while(pozfiu);
}
void dijkstra()
{
    int nod,father;
    heap[++cate]=1;
    poz[1]=1;///nod se afla pe pozitia poz[nod] in heap
    while(cate)
    {
        nod=heap[1];
        heap[1]=heap[cate--];
        poz[heap[1]]=1;
        down(heap[1],1);
        for(int i=0;i<graph[nod].size();++i)
        {
            if(dist[nod]+graph[nod][i].co<dist[graph[nod][i].ve])
            {
                dist[graph[nod][i].ve]=dist[nod]+graph[nod][i].co;
                if(poz[graph[nod][i].ve])///se afla deja in heap
                    up(graph[nod][i].ve,poz[graph[nod][i].ve]);
                else
                {
                    heap[++cate]=graph[nod][i].ve;
                    poz[graph[nod][i].ve]=cate;
                    up(heap[cate],cate);
                }
            }
        }
    }
}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m,x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        graph[x].push_back({y,c});
    }
    for(int i=2;i<=n;++i) dist[i]=INF;
    dijkstra();
    for(int i=2;i<=n;++i)
        if(dist[i]==INF)
            g<<0<<' ';
        else
            g<<dist[i]<<' ';
    f.close();
    g.close();
    return 0;
}