#include<cstdio>
#include<set>
#include<vector>
#define inf 1<<30
#define NMax 50005
using namespace std;

int n,in[NMax];
vector<int> d;

struct Compar
{
    bool operator () (int i, int j)
    {
        return d[i]<d[j];
    }
};

vector<pair<int, int> > c[NMax];
vector<pair<int, int> >::iterator it;
multiset<int,Compar> q;

void Dijkstra ()
{
    d.assign(n+1,inf);
    d[1]=0;
    q.insert(1);
    in[1]=1;
    while (!q.empty())
    {
        int k=*q.begin();
        q.erase(q.begin());
        in[k]=0;
        for (it=c[k].begin(); it!=c[k].end(); ++it)
            if (d[it->first]>d[k]+(it->second))
            {
                if (in[it->first])
                    q.erase(it->first);
                else
                    in[it->first]=1;
                d[it->first]=d[k]+(it->second);
                q.insert(it->first);
            }
    }
}

int main ()
{
    int x,y,z,i,m;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        c[x].push_back(make_pair(y,z));
    }
    Dijkstra();
    for (i=2; i<=n; i++)
        printf("%d ",d[i]==inf ? 0 : d[i]);
    return 0;
}