#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct node
{
    int nr,c;
    node *next;
} *v[50005],*p;
int n,m,a,b,c,cul[50005],cost[50005];
queue <int> q;

void dijkstra(int s)
{
    int w;
    q.push(s);
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        cul[w]=2;
        p=v[w];
        while(p)
        {
            if(!cul[p->nr] || (cul[p->nr]==2&&cost[p->nr]>cost[w]+p->c) )
            {
                cul[p->nr]=1;
                q.push(p->nr);
                cost[p->nr]=cost[w]+p->c;
            }
            else if(cost[p->nr]>cost[w]+p->c) cost[p->nr]=cost[w]+p->c;
            p=p->next;
        }
    }

}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        p=new node;
        p->nr=b;
        p->c=c;
        p->next=v[a];
        v[a]=p;
    }
    dijkstra(1);
    for(i=2;i<=n;++i) g<<cost[i]<<' ';
    g<<'\n';
    f.close(); g.close();
    return 0;
}