using namespace std;
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#define maxn 50001
#define oo 0x3f3f3f3f
#define pb push_back
struct nod { int x, c;nod *n;};
nod *a[maxn];
int d[maxn],n;
struct cmp{
    bool operator()(const int &a, const int &b)const
    {
            if(d[a]>d[b]) return 1;
            return 0;
    }
};
void read()
{
    int m, p, q, c;
    nod *t;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    while(m--)
    {
            scanf("%d %d %d\n", &p, &q, &c);
            t=new nod;
            t->x=q;
            t->c=c;
            t->n=a[p];
            a[p]=t;
            
    }
}
void dijkstra()
{
    priority_queue<int, vector<int>, cmp>Q;
    Q.push(1);
    memset(d, oo, sizeof(d));
    d[1]=0;
    int u;
   nod *it;
    while(!Q.empty())
    {
            u=Q.top();
            Q.pop();
 
            for(it=a[u]; it ;it=it->n)
                if(d[u]+it->c < d[it->x])
                {
                        d[it->x]=d[u]+it->c;
                         Q.push(it->x);
                        
                }
    }
    int i;
    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;
    freopen("dijkstra.out","w",stdout);
    for(i=2;i<=n;++i)printf("%d ", d[i]);
    printf("\n");
}
int main()
{
    read();
    dijkstra();
    return 0;
}