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(){}; nod(int a, int b){x=a;c=b;};};

vector<nod>a[maxn];

int d[maxn],n;

void read()
{
    int m, p, q, c;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    while(m--)
    {
	scanf("%d %d %d\n", &p, &q, &c);
	a[p].pb(nod(q, c));
    }
}

void bell()
{
    queue<int>Q;
    Q.push(1);
    bool use[maxn];
    memset(use, 0,sizeof(use));
    memset(d, oo, sizeof(d));
    d[1]=0;
    use[1]=1;
    int u;
    vector<nod>::iterator it;

    while(!Q.empty())
    {
	u=Q.front();
	Q.pop();
	use[u]=0;

	for(it=a[u].begin();it!=a[u].end();++it)
	    if(d[u]+it->c < d[it->x])
	    {
		d[it->x]=d[u]+it->c;
		if(!use[it->x])
		{
		    Q.push(it->x);
		    use[it->x]=1;
		}
	    }
    }

    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();
    bell();
    return 0;
}