#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#define maxn 50003
#define INF 0x3f3f3f3f

using namespace std;

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

struct nod
{
    int w;
    int dis;
}one;
vector<nod>a[maxn];

int i,j,n,dis[maxn],k,m,x,y,z;

bool been[maxn];

queue<int>Q;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        one.w=y;
        one.dis=z;
        a[x].push_back(one);
    }

    memset(been,false,sizeof(been));
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
    been[1]=true;
    Q.push(1);
    while(!Q.empty())
    {
        k=Q.front();
        Q.pop();
        been[k]=false;
        for(vector<nod>::iterator it=a[k].begin();it!=a[k].end();++it)
            if(dis[k]+it->dis<dis[it->w])
            {
                dis[it->w]=dis[k]+it->dis;
                if(been[it->w]==false)
                    Q.push(it->w),been[it->w]=true;
            }
    }

    for(i=2;i<=n;++i)
        g<<(dis[i]<INF?dis[i]:0)<<" ";
    g<<"\n";

    f.close();
    g.close();

    return 0;
}