#include <queue>
#include <cstdio>
#include <bitset>
using namespace std;

int n,m1;
vector<pair<int,int> > m[50004];
int d[50004];
bitset<50004> viz;

class mycomp
{
public:
    bool operator() (int a,int b)
    {
        return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,mycomp> q;

int main()
{
    int i,n1,n2,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(;m1;m1--)
    {
        scanf("%d%d%d",&n1,&n2,&c);
        m[n1].push_back( make_pair(n2,c) );
    }
    for(i=1;i<=n;i++) d[i]=0x7fffffff;
    d[1]=0;
    q.push(1);
    int nod;
    vector<pair<int,int> >::iterator it;

    while(!q.empty())
    {
        nod=q.top(); q.pop();
        if(!viz[nod])
        {
            viz[nod]=1;
            for(it=m[nod].begin();it!=m[nod].end();it++)
                if( d[it->first ]> d[nod] + it->second )
                {
                    d[it-> first]=d[nod]+it->second;
                    q.push(it->first);
                }
        }
    }

    for(i=2;i<=n;i++) if(d[i]!=0x7fffffff) printf("%d ",d[i]);
                                     else printf("0 ");
    fclose(stdin);
    fclose(stdout);
    return 0;
}