#include <iostream>
#include <fstream>
#include <queue>
#include <limits>
#define nmax 50001
using namespace std;

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

int n,m,drum[nmax];
struct nod
{
    int nr;
    int cost;
    nod *p;
}v[nmax];

queue <nod> q;

void add(int a,int b,int c)
{
    nod *q = new nod;
    q->p = v[a].p;
    q->nr = b;
    q->cost = c;
    v[a].p = q;
}
void read()
{
    f>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        add(a,b,c);
    }
}
void solve()
{
    for(int i=2;i<=n;i++)drum[i]=999999999;
    for(int i=1;i<=n;i++)v[i].nr = i;
    q.push(v[1]);
    while(!q.empty())
    {
       for(nod *z=q.front().p; z!=NULL; z=z->p)
       {
           if(drum[z->nr] > drum[q.front().nr] + z->cost)
           {
               drum[z->nr] = drum[q.front().nr] + z->cost;
               q.push(v[z->nr]);
           }
       }
       q.pop();
    }
}
void write()
{
    for(int i=2;i<=n;i++)g<<drum[i]<<" ";
}
int main()
{
    read();
    solve();
    write();
    return 0;
}